[백준] 12015번 가장 긴 증가하는 부분 수열 2

사용 언어 - Python3

120154번: 덱 (골드5, 큐)

문제 ★이분 탐색 문제★

12015번: 가장 긴 증가하는 부분 수열 2

 

 

정답

이분탐색으로 시간복잡도 O(nlogn) 개선

(코드 풀이)

ans=[0] 리스트에 값 비교하면서 append 해주기

ans[-1] ans의 가장 마지막 값이 i보다 작으면 ans에 append해준다.

그렇지 않다면, 이분탐색으로 인덱스 mid값을 조정해준다.

ans[mid]가 i보다 작으면 start = mid+1, i보다 크면 end = mid로 범위를 업데이트해준다.

ans[end] = i로 업데이트한다.

len(ans)에서 [0]을 뺀 len(ans)-1을 출력한다.

# 정답
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
ans = [0]

for i in a:
    if ans[-1] < i:
        ans.append(i)
    else:
        start = 0
        end = len(ans)
        
        while start < end:
            mid = (start+end)//2
            if ans[mid] < i:
                start = mid+1
            else:
                end = mid
        ans[end] = i
print(len(ans)-1) #0 빼기

(예) a = [10, 20, 10, 30, 20, 50], ans = [0]

ans[-1] < 10 만족

ans.append(10)

ans = [0,10]

 

ans[-1] < 20 만족

ans.append(20)

ans = [0, 10, 20]

 

ans[-1] < 10 만족X

start = 0 / end = len(ans) = 3

mid = (0+3)//2 = 1

ans[1] < 10 만족X

start = 0 / end = mid = 1

mid = (0+1)//2 = 0

end = mid = 0 while문 끝

ans[0] = 10

ans = [10 10 20]

 

ans[-1] < 30 만족

ans.append(30)

ans = [10 10 20 30]

 

ans[-1] < 20 만족X

start = 0 / end = len(ans) = 4

mid = (0+4)//2 = 2

ans[2] < 20 만족X

start = 0 / end = mid = 2

mid = (0+2)//2 = 1

ans[1] < 20 만족X

start = 0 / end = mid = 1

mid = (0+1)//2 = 0

ans[0]  = 20

ans = [20 10 20 30]

 

---

레퍼런스

• 정답 참고

최장 증가 부분 수열(LIS) 알고리즘

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부