[백준] 2170 - 선 긋기

1. 문제

2170번: 선 긋기

2. 개요

선들의 시작점과 끝점이 주어졌을 때, 중복으로 그어진 부분을 제외한 모든 선들의 길이의 합을 구하는 문제.

3. 코드 및 추가내용

import sys

N = int(sys.stdin.readline())

lines = []
for i in range(N):
    lines.append(list(map(int,sys.stdin.readline().split())))

lines.sort(key = lambda x : (x[0], -x[1]))

start, end = lines[0][0], lines[0][1]
ans = 0
for s, e in lines[1:]:
    if e <= end:
        continue

    elif s <= end:
        end = e

    else:
        ans += end - start
        start, end = s, e

ans += end - start
print(ans)

일단 시작점이 낮은 값을 1순위, 도착점이 높은 값을 2순위로 정렬한다.

첫 값 시작점과 도착점을 통합 선의 시작점, 도착점으로 잡고 다음 값부터 탐색을 시작한다.

만약 선의 도착점이 통합 선의 도착점보다 작다면, 전체가 중복이므로 continue

도착점은 더 큰데, 시작점만 통합 선의 도착점보다 작다면 길이가 늘어나는 셈이므로 통합 선의 도착점을 갱신한다.

한 선의 시작점이 현재 통합 선의 도착점보다 더 크다면 현재 통합 선의 길이를 결과에 더하고 현재의 선을 새로운 통합 선으로 잡아준다.

탐색이 모두 끝났다면 현재 들고있는 통합 선의 길이까지 계산하여 결과에 더한 뒤 출력한다.