꼬인 전깃줄


몇개 풀어봤던 DP를 이용한 LIS 문제였는데, 이 문제는 입력의 갯수가 최대 10만개여서 시간초과가 발생했다. 고민하다 결국 블로그를 참고해서 풀었다. 이진 검색을 활용해 시간복잡도를 줄인 풀이였는데 이번주 내로 반드시 다시 풀어봐야겠다.

[다시 풀어보기] ✔ - 2020.10.24


CODE

import sys
read=sys.stdin.readline

N=int(read())
num=list(map(int,read().split()))

dp=[num[0]]

def bin_search(x):
    a=0
    b=len(dp)-1
    while a<=b:
        mid=(a+b)//2
        if dp[mid]>x:
            if 0<=mid-1 and dp[mid-1]<x:
                dp[mid]=x
                break
            elif dp[0]>x:
                dp[0]=x
                break
            else:
                b=mid-1
        else:
            a=mid+1

for n in num[1:]:
    if n > dp[-1]: dp.append(n)
    else: bin_search(n)

print(N-len(dp))



전깃줄-2

이 문제도 결국 블로그를 참고해 풀었다…! 굉장히 찜찜하다. 이번주 내로 다시 풀어보자.

[다시 풀어보기]


CODE

import sys
sys.stdin = open("input.txt","rt")
read=sys.stdin.readline

N=int(read())
lines=list(list(map(int,read().split())) for _ in range(N))
num=[]
lines.sort()
for a,b in lines:
    num.append(b)
give_start=dict()
for a,b in lines:
    give_start[b]=a


dp=[num[0]]
check=list(0 for _ in range(N))
check[0]=1

def bin_search(x):
    a=0
    b=len(dp)-1
    while a<=b:
        mid=(a+b)//2
        if dp[mid]>x:
            if 0<=mid-1 and dp[mid-1]<x:
                dp[mid]=x
                check[i]=mid+1
                break
            elif dp[0]>x:
                dp[0]=x
                check[i]=1
                break
            else:
                b=mid-1
        else:
            a=mid+1

for i in range(1,N):
    n=num[i]
    if n > dp[-1]:
        dp.append(n)
        check[i]=len(dp)
    else:
        bin_search(n)

#print(dp)
print(N-len(dp))
#print(num)
#print(check)

cnt=len(dp)
semi_answer=[]
for i in range(N-1,-1,-1):
    if check[i]==cnt:
        cnt-=1
        semi_answer.append(num[i])

#print(semi_answer)
num=set(num)
semi_answer=set(semi_answer)
num-=semi_answer
num=list(num)
answer=[]
for n in num:
    answer.append(give_start[n])
answer.sort()
for a in answer:
    print(a)