정렬-스위핑

이론

📖 스위핑

• 특정 선이나 공간을 한쪽에서부터 스캔하면서 쓸어가는 알고리즘.
• '정렬' 을 이용해서 구현.

문제풀이

📖 백준 2170

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

# keypoint : 스위핑

# 배열로 할 경우 20억개나 되기 때문에 시간초과에 유의.

import sys
input=sys.stdin.readline

n=int(input())

line=[]   # 선 정보.
for i in range(n):
    x,y=map(int,input().split())
    line.append([x,y])

line.sort(key=lambda x:x[0])   # 시작좌표 기준으로 정렬.

start=line[0][0]
end=line[0][1]

answer=0
for i in range(1,n):
    n_start,n_end=line[i]
    # 겹치지 않는 경우.
    if n_start>end:
        answer+=(end-start)  # 기존 값 answer에 더하기.
        start,end=n_start,n_end   # 갱신
    # 겹치는 경우.
    else:
        end=max(end,n_end)

answer+=(end-start)
print(answer)

✍️ 공부한 내용을 정리하는 공간이기 때문에, 정확하지 않은 사실이 들어갈 수 있습니다.