[백준] 1689 겹치는 선분 (Python)

🔗 문제 링크

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

💻 코드

import sys

input = sys.stdin.readline 

n = int(input())
lines = []

for _ in range(n):
    s,e = map(int,input().split())
    lines.append((s,1))
    lines.append((e,-1))

lines.sort()
print(lines)

result = 0
cnt = 0 

for i, j in lines:
    cnt += j 
    result = max(cnt,result)

print(result)

🧩 풀이

이 문제를 풀기 위해서는 스위핑 알고리즘을 알아야했다. 직선에서 시작점을 기준으로 끝나는 지점까지 스캔하는데, 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 기준을 세워 구해야 한다. 각 선마다 모든 구간을 확인하면 O(N^2)라서 시간초과가 발생한다. 따라서 왼쪽에서 오른쪽으로 한 번만 탐색해야한다.

• 시작점은 +1, 끝점은 -1로해서 한 번씩 확인해서 겹치는 구간의 최대값을 갱신한다.

• 왜 그리디 알고리즘일까?

  • 현재 시점에서 겹치는 선분 개수를 실시간으로 세며, 지금까지 본 것 중 가장 많은 개수 (max)를 선택

  • 그리디 알고리즘은 지금 당장 최선의 선택이 전체적으로도 최선, 부분 문제의 최적해가 전체 문제의 최적해로 이어짐 2가지를 만족한다.