[BOJ] 2170 선 긋기

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

최근에 했던 코딩테스트에서 처음 보는 유형의 문제가 나와서 O(n^2) 코드밖에 떠오르지 않았는데 다음에 비슷한 문제가 나오면 어떻게 대응해야할 지 확인하기 위해서 지피티 선생님의 지혜를 빌려 어떤 유형의 문제인지 확인했고, 그 중 하나이다.

겹치는 구간이 있을 수도 있는 선을 긋는데 그렇게 그었을 때 길이를 구하는 문제이다.

지피티 선생님의 도움을 받아서 라인 스윕이라는 알고리즘을 해결하는 코드를 받았었다.

def count_overlaps(horizontal_segments, vertical_lines):
    events = []
    
    # Create events for horizontal segments
    for x1, x2 in horizontal_segments:
        events.append((x1, 'start'))
        events.append((x2 + 1, 'end'))
    
    # Create events for vertical lines
    for v in vertical_lines:
        events.append((v, 'query'))
    
    # Sort events: prioritize 'start' < 'query' < 'end' for same x-coordinate
    events.sort(key=lambda x: (x[0], x[1] != 'start', x[1] == 'end'))
    
    active_segments = 0
    result = defaultdict(int)
    
    # Process events
    for x, event_type in events:
        if event_type == 'start':
            active_segments += 1
        elif event_type == 'end':
            active_segments -= 1
        elif event_type == 'query':
            result[x] = active_segments
    
    return [result[v] for v in vertical_lines]

당시 풀었던 문제를 기반으로 물어봤었는데, 각 선분의 시작과 끝에 start, end라는 표시를 하고 중간에 확인이 필요한 지점에는 query라는 거를 설정했다.
그러고 event를 돌면서 start가 있으면 현재 겹치는 선분이 몇 개 있는지(active segment)의 수를 늘리고, end를 만나면 겹치는 선분을 하나 제거한다. 중간에 query 만나면 거기서 기록을 해줬다.

이런 방식을 따와서 query만 빼고 코드를 비슷하게 만들었다.

import sys

input = sys.stdin.readline

event = []

for _ in range(int(input())):
  x, y = map(int, input().split())
  
  event.append((x, 'start'))
  event.append((y, 'end'))
  

event.sort(key = lambda x: (x[0], x[1] != 'start', x[1] == 'end'))


answer = 0

status = 0
start = 0
end = 0
for x, type in event:
  if type == 'start':
    if status == 0:
      start = x
    status += 1
  elif type == 'end':
    status -= 1
  
  if status == 0:
    answer += x - start

print(answer)

그런데 시간초과로 실패했다. 아무래도 event를 start, end로 분리하니까 원래 백만에서 2백만으로 경우가 증가해서 그런 것 같다.

다른 코드를 살펴봤다.

import sys
input = sys.stdin.readline

n = int(input())
lines = [tuple(map(int, input().split())) for _ in range(n)]

lines.sort()

left = lines[0][0]
right = lines[0][1]

ans = 0

for i in range(1, n):
  if right >= lines[i][1]:
    continue
  
  elif lines[i][0] <= right < lines[i][1]:
    right = lines[i][1]
  
  elif right < lines[i][0]:
    ans += right - left
    left = lines[i][0]
    right = lines[i][1]
    
ans += right - left
print(ans)

여기는 튜플에 각 시작과 끝을 동시에 저장했고, 정렬을 한 후에 방식은 비슷하게 진행됐다.
첫 선분의 시작과 끝을 기록한 후에, 끝이 다른 선분을 포함하면 넘기고, 다른 선분 사이에 있으면 끝을 늘려주고, 다른 선분보다 짧으면 시작과 끝을 업데이트하는 방식으로 구했다.

생각해보니 지피티가 알려준 알고리즘은 선분이 겹치는 상황에서 수직선이 있을 때, 각 수직선마다 몇 개의 선분이 겹치는지 구할 때 사용하는 알고리즘이었고, 이 문제는 선분이 겹칠 때 겹치는 거 포함해서 길이가 어떻게 되는지 묻는 문제였다.

두 가지 알고리즘을 기억해서 적절하게 활용할 필요가 있겠다.