백준(BOJ) 2170 선 긋기(Python)

 

문제 내용

 

스위핑 문제.

좌표를 시작점, 끝점 기준으로 오름차순 정렬한 뒤, 값을 하나씩 참고하며 현재 선분의 왼쪽 좌표값보다 현재 참고하는 선분의 왼쪽 좌표값이 크고 오른쪽 좌표값이 더 작다면 선분을 연장한다. 즉, 선분의 길이에 (현재 참고하는 선분의 왼쪽 좌표값)-(현재 선분의 왼쪽 좌표값)만큼 선분의 총 길이에 더해주고, 현재 선분의 왼쪽 좌표값을 현재 참고하는 선분의 왼쪽 좌표값으로 변경한다. 그외에는 새로운 선분이 추가되므로 현재 참고하는 선분의 왼쪽 좌표값을 현재 선분의 왼쪽 좌표값으로 변경한 뒤 선분의 길이에 (현재 참고하는 선분의 왼쪽 좌표값)-(현재 참고하는 선분의 오른쪽 좌표값)을 더한 후 현재 참고하는 선분의 오른쪽 좌표값을 현재 선분의 오른쪽 좌표값으로, 현재 참고하는 선분의 왼쪽 좌표값을 현재 선분의 왼쪽 좌표값으로 변경한다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n=int(input())
L=[]
for i in range(n):
    L.append(list(map(int,input().split())))
L.sort()
h=0
r=-10e10
l=-10e10
for a,b in L:
    if b>l:
        if a<=l:
            h+=b-l
            l=b
        else:
            h+=b-a
            l=b
            r=a
print(h)

 

스위핑 문제는 시간 초과가 매우 잘 터지는 것 같다.

처음에 불필요한 연산을 크게 신경쓰지 않고 그냥 몇 번 제출했는데 다 시간 초과가 터져서 완전 신경써서 제출하니 통과했다.

열심히 해야겠다.