[백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python

[백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python

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

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

가장 긴 증가하는 부분 수열 1을 풀었던 방식으로는 해결하지 못한다.

수열 A의 원소의 개수도 늘어났고, A를 이루는 원소의 범위도 넓어졌다. O(N^2)의 방법인 이중 for문으로는 시간 안에 통과하지 못한다는 것을 알 수 있다.

 

질문 게시판에서 이중 for문을 돌릴 때 안쪽 for문에서 세그먼트 트리나 이진 탐색으로 시간 복잡도를 줄일 수 있다고 하는 글을 봤지만 이해가 되지 않아 다른 블로그들을 찾아봤다.

 

처음에 다른 블로그들을 볼 때 이게 왜 증가하는 부분 수열이 되는건지 이해가 안 됐었는데, 다들 올라온 방식이 가장 긴 증가하는 부분 수열 자체를 구하는 것이 아닌 가장 긴 길이를 구하기 위해 수열의 형태를 사용했던 것이었다.

아래의 블로그를 참고했었다.

https://sihyungyou.github.io/baekjoon-12015/

 

헷갈렸던 부분은 다음과 같다. 수열이 [10, 20, 50, 70, 30, 80]으로 주어져있다면, 가장 긴 길이를 구하기 위해 사용했던 수열에는 다음과 같은 순서로 채워질 것이다.

10
10 20
10 20 50
10 20 50 70
10 20 30 70
10 20 30 70 80

중간에 이탤릭체로 해놓은 곳을 보면 30이 추가될때 30이 들어갈 수 있는 위치인 50을 30으로 바꾸게 된다. 하지만 저렇게 생성된 부분 수열 [10, 20, 30 70]은 실제로는 생성될 수 없는 수열이다.

그러나 문제 자체가 수열을 구하는 것이 아닌 수열의 길이를 구하는 것이기 때문에 상관이 없게 된다. 30을 추가하더라도 가장 긴 증가하는 부분 수열의 길이는 4라는 것은 변하지 않기 때문이다.

 

수열이 [10, 20, 50, 70, 30, 35, 80] 일 때도 마찬가지이다. 다음과 같은 순서로 채워질 것이다.

10
10 20
10 20 50
10 20 50 70
10 20 30 70
10 20 30 35 
10 20 30 35 80

30이 추가될 때, 35가 추가될 때, 가장 긴 부분 증가 수열의 길이는 4 임은 변함이 없다는 것은 실제로 알 수 있다.

물론 30일 때 가장 긴 부분 증가 수열은 [10, 20, 30, 70]이 아니라 [10, 20, 50, 70]이지만 말이다.

그리고 80까지 주어지면 [10, 20, 50, 70, 80]이든 [10, 20, 30, 35, 80]이든 길이는 5가 된다.

 

그래서 해당 위치를 찾아주기 위해서 두가지 방법을 사용했다.

하나는 직접 이분탐색으로 해당 위치를 찾아주었고, 다른 하나는 bisect를 사용해주었다.

bisect에서 넣으려는 A가 이미 있다면 그 A의 위치를 찾아야 하기 때문에 bisect_left와 bisect_right(=bisect) 중에 무엇을 bisect_left를 사용해야 한다.

 

bisect는 아래 블로그들에서 비교한 결과를 볼 수 있다.

https://blog.naver.com/PostView.nhn?blogId=wideeyed&logNo=221389084876&proxyReferer=https:%2F%2Fwww.google.com%2F

https://soooprmx.com/archives/8722

 

통과한 처리 시간은 bisect를 사용한 것이 더 빨랐다.

# Use Binary Search
import sys

def find(target):
    l, h = 1, len(stack)-1
    while l < h:
        m = (l+h)//2
        if stack[m] < target:
            l = m+1
        elif stack[m] > target:
            h = m
        else:
            l = h = m
    return h

l = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
stack = [0]

for a in arr:
    if stack[-1] < a:
        stack.append(a)
    else:
        stack[find(a)] = a

print(len(stack)-1)

# Use Bisect module
import sys
from bisect import bisect_left

l = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
stack = [0]

for a in arr:
    if stack[-1] < a:
        stack.append(a)
    else:
        stack[bisect_left(stack, a)] = a

print(len(stack)-1)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다