[백준/python] 1689 겹치는 선분

1. 리스트를 활용한 방법

import sys
input = sys.stdin.readline

arr = []
for _ in range(int(input())):
    s,e = map(int,input().split())
    arr.append((s,1))
    arr.append((e,-1))

tmp,ans = 0,0
for k,v in sorted(arr):
    tmp += v
    ans = max(ans,tmp)
print(ans)

2. 딕셔너리를 활용한 방법

import sys
input = sys.stdin.readline

data = dict()
for _ in range(int(input())):
    s,e = map(int,input().split())
    data[s] = data.get(s,0)+1
    data[e] = data.get(e,0)-1

tmp,ans = 0,0
for key in sorted(data):
    tmp += data[key]
    ans = max(ans,tmp)
print(ans)

들어오는 입력이 최대 1,000,000개 이므로, 이중 for문만 해도 1조 번의 연산이 필요하기에 시간에 대한 고려는 필수적입니다.

스위핑 테크닉을 활용해 시작점이면 +1, 도착점이면 -1을 셈하며 한번의 순회로 계산이 마무리되게 할 수 있습니다.

이렇게 계산하면, $O(N log N)$의 시간복잡도가 발생합니다.

또한, 100만개의 입력에서 겹치는 숫자 또한 존재할 수 있으므로, 일반적인 경우에 딕셔너리를 활용해 각 시작점과 끝점의 좌표에 더해질 값을 미리 계산해두고 순회를 한다면 더 적은 양의 순회로 계산을 마칠 수 있습니다.

이로 인해 공간복잡도 또한 개선된 모습을 보여주었습니다.