[BOJ] 2170 - 선 긋기

1. 문제 링크

2170번 - 선 긋기

2. 걸린 시간

10분

3. 문제 풀이

input = open(0).readline

dots = []

for i in range(n := int(input())):
    x, y = map(int, input().split())
    dots.append((x, 1))
    dots.append((y, -1))

dots.sort()

cnt = 0
total = 0

for n, d in dots:
    cnt += d
    if cnt == 1 and d == 1:  # start면서 겹치는 것 X
        start = n
    elif cnt == 0 and d == -1:  # end면서 겹치는 것 X
        end =  n
        total += (end - start)

print(total)

스위핑 알고리즘을 사용해서 간단하게 풀었다.

• d = 1 -> start (선의 시작점)
• d = 0 -> end (선의 끝점)

겹치는 선의 개수를 나타내는 cnt에 d를 더해주면서 다음의 조건에 따라 처리한다.

• cnt == 1 and d == 1 = 선의 시작점(start)이면서 겹치는 선이 없음
  • start = n
• cnt == 0 and d == -1 = 선의 끝점(end)이면서 겹치는 선이 없음
  • total += (end - start)