[BOJ 2170] 파이썬으로 선 긋기

1. 핵심 아이디어

그어야 할 선이 (N = 1,000,000)이므로 모든 좌표를 일일이 대조하면 시간 초과
=> 선들을 시작점 기준으로 정렬하는 아이디어 도입
1. 모든 선들을 X를 기준으로 오름차순 정렬
2. 앞에서부터 선을 하나씩 확인하면서 현재까지 이어진 선의 start와 end 갱신

2. 선을 합치는 3가지 경우의 수

정렬된 상태에서 새로운 선을 만나면 3가지를 파악하면 된다.

• 완전히 겹침 : 새 선이 현재 선 안에 포함되는 경우 -> skip
• 일부 겹침 : 시작점은 현재 범위 안인데, 끝점이 더 뒤에 있는 경우 -> 현재 선의 end를 next_end로 늘리기
• 끊김 : 새 선의 시작점이 현재 선의 끝점보다 뒤에 있는 경우 -> 지금까지 길이를 더하고, 새 선을 기준으로 다시 시작

3. 코드

import sys

def solve():
    input = sys.stdin.read().splitlines()
    if not input:
        return
    
    n = int(input[0])
    lines = []
    
    for i in range(1, n + 1):
        lines.append(list(map(int, input[i].split())))
    
    # 1. 시작점 기준 정렬
    lines.sort()
    
    # 2. 첫 번째 선으로 초기화
    curr_start = lines[0][0]
    curr_end = lines[0][1]
    total_length = 0
    
    for i in range(1, n):
        next_start, next_end = lines[i]
        
        # 선이 겹치거나 이어지는 경우
        if next_start <= curr_end:
            # 더 긴 쪽으로 끝점 갱신
            curr_end = max(curr_end, next_end)
        else:
            # 선이 끊긴 경우 지금까지의 길이를 더함
            total_length += (curr_end - curr_start)
            # 새로운 선으로 교체
            curr_start = next_start
            curr_end = next_end
            
    # 마지막으로 남아있는 선의 길이 추가
    total_length += (curr_end - curr_start)
    print(total_length)

solve()