[Python/백준] 2170 선 긋기

https://www.acmicpc.net/problem/2170

2170번: 선 긋기

<문제 해설>

그리디 문제이다.

1. x좌표를 기준으로 오름차순으로 정렬한다.
2. 첫번째 x좌표와 y좌표를 기록한다.
3. 2번째  x좌표가 첫번째 y좌표보다 앞에있다면 2번째와 첫번째 y좌표를 비교해서 더 큰 값으로 y좌표를 기록한다.(여기서 x좌표는 정렬되어 있기 때문에 2번째 x좌표가 첫번째 x좌표보다 앞에 있을 수가 없다.)
4. 2번째 x좌표가 첫번째 y좌표보다 뒤에 있다면 첫번째 x좌표와 y좌표의 차를 구해서 output에 더해준다.(길이를 더해준다.) 그후 2번째 x좌표와 y좌표를 기록한다.
5. 이런식으로 x좌표가 뒤에있으면 output에 더해주기 앞에있으면 계속 기록해가는 식으로 값을 구해간다.

<예시>

문제에 올라와있는 예시를 약간 변형해서 예시를 만들고 윗 그림을 그렸다.

좌표 1 3일때 front에 1이 저장되고 back에 3이 저장된다.

좌표 2 5일때 2가 back에 저장되어 있는 3보다 작음으로 5와 3을 비교해서 큰 숫자인 5를 back에 기록한다.

좌표 3 5일때 3이 back에 저장되어 있는 3보다 작음으로 4와 5를 비교해서 큰 숫자인 5를 back에 기록한다.

좌표 6 7일때 6이 bakc에 저장되어 있는 5보다 큼으로 back - front를한 4를 output에 저장하고 front에 6 back에 7을 저장한다.

좌표를 모두 계산했으니 마지막으로 back - front를 output에 저장하고 출력한다. 답인 5가 출력된다.

<코드>

import sys
N = int(sys.stdin.readline())

lines = []

for i in range(N):
    lines.append(list(map(int,sys.stdin.readline().split())))

lines.sort()

front = lines[0][0]
back = lines[0][1]

output = 0

for i in range(1,N):
    if lines[i][0] <= back:
        back = max(lines[i][1],back)
    else:
        output += abs(back - front)
        front = lines[i][0]
        back = lines[i][1]

print(output + abs(back - front))

<코드 설명>

import sys //sys라이브러리 불러오기
N = int(sys.stdin.readline()) //N값 정수로 받아오기

lines = [] //lines배열 생성

for i in range(N): //N만큼 반복
    lines.append(list(map(int,sys.stdin.readline().split()))) //배열에 좌표값들 기록하기

lines.sort() //lines배열 정렬

front = lines[0][0] //첫 x좌표 front에 기록
back = lines[0][1] //첫 y좌표 back에 기록

output = 0 //출력값을 0으로 초기화

for i in range(1,N): //2번째부터 N만큼 반복
    if lines[i][0] <= back: //back보다 지금 좌표의 x가 작거나 같다면
        back = max(lines[i][1],back) //back이랑 지금 좌표의 y를 비교해서 큰값을 back에 저장
    else: //x좌표가 back보다 크다면
        output += abs(back - front) //output에 지금까지 기록된 줄의 길이를 더해주기
        front = lines[i][0] //front에 x좌표 저장
        back = lines[i][1] //back에 y좌표 저장

print(output + abs(back - front)) //x좌표 y좌표 차이 output에 더해서 출력