백준 2568 : 전깃줄 - 2 (Python)

본문 링크

from bisect import bisect_left
import sys
input=sys.stdin.readline

T=int(input())
L=[]
for i in range(T):
    a,b=map(int,input().split())
    L.append([a,b])
L.sort(key=lambda x:x[0])

dp=[]

check=[]
for i,j in L:
    if not dp:
        dp.append(j)
    if dp[-1]<j:
        dp.append(j)
        check.append( (len(dp)-1,j))
    else:
        index=bisect_left(dp,j)
        dp[index]=j
        check.append( ( index,j) )


answer=[]

last_index=len(dp)-1

for i in range(len(check)-1 , -1 , -1):
    if check[i][0]==last_index:
        answer.append(check[i][1])
        last_index-=1

print(T-len(dp))
A_line=[]

for i in range(-1,-T-1,-1):
    for j in range(len(answer)):
        if L[i][1]==answer[j]:
            A_line.append(L[i][0])


A_line.sort()
count=0

for i in range(T):
    P=0
    for j in range(len(A_line)):
        if L[i][0]==A_line[j]:
            P=1
    if P==0:
        print(L[i][0])

📌 어떻게 접근할 것인가?

이전의 전깃줄 1 문제 를 풀어봤다면 접근방법은 간단하다.

왼쪽의 전깃줄을 정렬하고 오른쪽 전기줄의 최장 연속 길이 부분 수열을 구하는 알고리즘을 사용하면 된다.

다만 까다로운 점은 전깃줄의 개수가 최대 100,000 이므로 $O(Nlog N)$ 안에 해결해야한다.

또한 개수도 구하고 없에야하는 전기줄도 구해야 하기 때문에 조금 복잡하다.

먼저 입력받을 리스트를 L.sort(key=lambda x:x[0]) 로 정렬해준다.

이후 bisect_left 함수를 통해서 $O(Nlog N)$ 으로 가장 긴 증가하는 부분수열을 구해준다.

이 방법은 가장 긴 증가하는 부분 수열 5 문제와 방법이 거의 똑같다.

이제 가장 긴 증가하는 부분수열을 구했으니 잘라야하는 전기줄을 구해야한다.

A_line 이라는 배열을 만들어 주고 이중반복문을 통해 리스트 L의 원소와 answer의 원소가 같은 지점을 구한다.
우리가 구하고자 하는것은 가장 긴 증가하는 부분수열에서 사용한 전기줄이 아니라
필요없는 전기줄을 구하는 것이므로 다시 이중 반복문을 통해 필요없는 전기줄을 A_line 리스트를 통해 확인해준다.

이후 필요없는 전기줄을 차례대로 출력한다.