[백준] 2170번: 선 긋기 Python - 스위핑 알고리즘, 정렬

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

2170번: 선 긋기

문제 첫인상은 별로 어렵지 않을 것 같아보였으나 (...) 왜 정답률이 30%대인지 알겠는 문제

i ) 선형적으로 문제를 풀어야 하니까 정렬 , 투포인터 , .. 등등을 떠올리게 되었다. 

ii ) 문제를 그려서 이해해보았다. 

한 선분을 기준으로, start와 end 가 선분의 양 끝점이라고 한다. 

이 경우 새로운 두 개의 점이 주어졌을 때 위의 그림과 같이 두가지 경우로 나뉘게 된다. 합쳐지거나, 합쳐지지 못하거나 두가지이다. 

주어지는 (x, y) 에 대해 오름차순 정렬을 한다. 오름차순 정렬을 통해 얻는 효과는 start 와 end 에 합쳐질 수 있는지 바로 직전에 갱신된 start, end 좌표 값과 x, y 값을 비교해서 합쳐지거나 합쳐지지 못한다는 것을 알 수 있다. 

합쳐지지 않는 경우는 end < x 인 경우이고, 합쳐지는 경우는 그 이외의 모든 경우일 것이다. 따라서 if - else 문으로 분기처리했다. 

즉, 이미 오름차순 정렬을 했으므로 x는 항상 더 큰 값만 나올 것이다!! 라는게 핵심이다

n = int(input())
answer = 0

points = []
for i in range(n):
    x, y = map(int, input().split())
    points.append((x, y))
points.sort()
s, e = points[0]
for i in range(1, n):
    x, y = points[i]
    if e < x: # 갱신해야 함
        answer += (e - s)
        s, e = x, y
    else:
        e = max(e, y)

answer += (e-s)
print(answer)