[Python/파이썬] 백준 2170번 선 긋기

2170번: 선 긋기

 

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

입력

첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

코드

import sys
input = sys.stdin.readline

n = int(input())
line = []
for _ in range(n):
    a, b = map(int, input().split())
    line.append([a, b])
line.sort()
ans = 0
s, e = line[0]
for i in range(1, n):
    if line[i][0] > e:
        ans += (e-s)
        s = line[i][0]
        e = line[i][1]
    else:
        e = max(e, line[i][1])
ans += (e-s)
print(ans)

입력받은 선들을 시작점 위치를 기준으로 오름차순 정렬한다.

정렬된 선들을 하나씩 살펴보며 현재 살펴보고 있는 선의 시작점(line[i][0])이 e보다 큰 지 확인한다. e보다 크다면 둘은 다른 선분이므로 앞의 선분 (s, e)의 길이를 ans에 더해주고 s, e의 값을 현재 보고 있던 선의 시작점과 끝점으로 갱신해준다. 만약 현재 보고 있는 선과 선분 (s, e)가 같은 선분 위에 있다면 e의 값만 e와 현재 선의 끝점(line[i][1]) 중 큰 값으로 갱신해준다. for문을 다 돌고 난 다음에는 마지막 선분이 ans에 더해지지 않은 상태이므로 선분 (s, e)의 길이를 한 번 더해주면 답이다.