[boj] 14003,11722 가장 긴 증가 부분 수열 (feat. bisect)

오늘은 가장 긴 증가/감소 부분수열 시리즈를 쭉 풀어보았다.

 

1. 11722번

www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

 

[접근법 1]

 

나는 처음에는 좀 무식하게 LCS로 접근했다.

def solution(X,Y):
    n=len(X)
    m=len(Y)
    T=[[0 for j in range(m+1)] for i in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if X[i-1]==Y[j-1]:
                T[i][j]=1+T[i-1][j-1]
            else:
                T[i][j]=max(T[i-1][j],T[i][j-1])
    
    return T[n][m]
        

N=int(input())
l=list(map(int, input().split(' ')))
sl=sorted(list(set(l)),reverse=True)
print(solution(l,sl))

정렬된 sl 리스트와 가장 많이 겹치는 것을 찾는 방식으로 접근했다.

맞았으나, 다른 분들보다 너무 긴 시간이 걸린 것을 확인..

다른 분들의 코드를 읽어보기 시작했다.

[접근법 2]

나만의 수도코드 ><

candidate 리스트 (가장 긴 수열이 될 리스트)에 대해

조건이 맞으면 계속 리스트를 증가시키고,

조건이 맞지 않으면 (즉, 역방향성을 띄면) 해당 원소가 candidate list 어디 인덱스에 있으면 순방향성을 띄는지 확인하고 교체한다.

여기서 해당 원소가 candidate list 어디 인덱스에 있는지 확인할 때 '이분탐색'을 사용한다.

def solution(s,e,t):
    while s<e:
        m=(s+e)//2
        if result[m]>t:
            s=m+1
        else:
            e=m
    return e

N=int(input())
l=list(map(int, input().split(' ')))
result=[]
for idx,i in enumerate(l):
    if idx==0:
        result.append(i)
    elif result[-1]>i:
        result.append(i)
    elif result[-1]==i:
        pass
    else:
        #자신의 위치를 찾아가야함.
        idx=solution(0,len(result),i)
        result[idx]=i
print(len(result))

 

 

결과는 아주 나이스!

 

---

그렇게 나는 신나게 다음 문제를 풀었다.

www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

그런데.. 위의 합분해 방식으로는 계속 시간초과가 났다.

방법을 찾아보니 bisect 라는 라이브러리를 알게되었다. (앞으로 자주 쓸 것같다.)

이분탐색 기법으로 범위리스트와 원소가 주어졌을때, 원소가 리스트의 몇번째 인덱스범위에 존재하는지 알려주는 리스트이다.

무슨말인지 모르겠다. 일단 코드를 보자.

이렇게

<=1 : index 0

<=10 : index 1

<=20 : index 2

을 알려준다.

bisect_left는 리스트 원소 왼쪽범위를 리턴하고, bisect_right는 리스트 오른쪽 범위를 리턴한다.

 

이 모듈을 가지고 문제를 쉽게 해결할 수 있었다. (기본 모듈이니 자주 쓸 것 같다.)

import sys
import bisect
N=int(input())
l=list(map(int, input().split(' ')))
result=[]
ans=[]#후보군들을 다 모아둠.
for idx,i in enumerate(l):
    if idx==0:
        result.append(i)
        ans.append((0,i))
    elif result[-1]<i:
        result.append(i)
        ans.append((len(result)-1,i))
    elif result[-1]==i:
        pass
    else:
        #자신의 위치를 찾아가야함.
        idx=bisect.bisect_left(result,i)
        result[idx]=i
        ans.append((idx,i))

print(len(result))
t=len(result)
s=[]
for idx,i in ans[::-1]:
    if idx==t-1:
        s.append(i)
        t-=1
print(' '.join(list(map(str,s[::-1]))))

---

여담으로 이친구덕에 (이친구가 무려 골드 1 문제다 ><) 골드 4로 레벨업! 오예오예