[백준] 2568. 전깃줄 - 2 - Python

[Platinum V]

 

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

2568번: 전깃줄 - 2

 

풀이

이분탐색을 이용한 LIS - O(NlogN) 문제. 아래 두 문제를 참고하면 쉽게 풀이할 수 있다.

[백준] 2565. 전깃줄 - Python

[백준] 14003. 가장 긴 증가하는 부분 수열 5 - Python

 

AC.

import bisect
from collections import deque
n = int(input())
 
lines = []
for _ in range(n):
    lines.append(list(map(int, input().split())))
lines = sorted(lines, key = lambda x: x[0])
 
res = []
index = []
for s, e in lines:
    a = bisect.bisect_left(res, e)
    if a == len(res):
        res.append(e)
    else:
        res[a] = e
        
    index.append(a)
 
cnt = len(res)-1
q = deque()
for i in range(len(index)-1, -1, -1):
    if index[i] == cnt:
        cnt -= 1
    else:
        # LIS에 포함되지 않는 경우를 저장.
        q.appendleft(lines[i])
 
print(len(lines) - len(res))
for k in q:
    print(k[0])