[백준 / BOJ][Python] 2170 - 선 긋기

[백준 / BOJ][Python] 2170 - 선 긋기

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

2170번: 선 긋기

문제 풀이

기초 수준의 스위핑 문제. 우선 시작점과 끝점을 기준으로 선들을 정렬한다. 이후 기존의 선에 추가하여 덧붙일 수 있다면 붙이고, 기존 선의 끝점보다 새로 긋는 선의 출발점이 뒤에 있다면 이전 선의 길이를 정답에 더하고 새로운 선을 긋는다. 

코드

import sys
input = sys.stdin.readline

n = int(input())
line_list = [] #선들의 집합
for _ in range(n):
    line_list.append(tuple(map(int, input().split())))
line_list.sort() #시작점, 끝점을 기준으로 오름차순 정렬
ans = 0
s, e = -10 ** 10, -10 ** 10 #현재 선의 시작점, 끝점
for a, b in line_list:
    if a > e: #새로 긋는 선의 시작점이 기존 선의 끝점보다 크다면
        ans += e - s #기존 선의 길이를 정답에 추가
        s, e = a, b #기존의 선을 새로 긋는 선으로 교체
    else:
        e = max(e, b) #기존 선의 끝점은 max(새로 긋는 선의 끝점, 기존 선의 끝점)
ans += e - s #마지막으로 남아있는 선의 길이 정답에 추가
print(ans)