[Baekjoon, Python] 12015 번: 가장 긴 증가하는 부분 수열 2

도입

백준 단계별 풀기에서 이분탐색 일곱 번째, 마지막 문제이다.

백준 12015번 문제, 입력, 출력

---

백준 12015번 입출력 예제 1

---

풀이

0. 2가지 풀이를 할 예정, 이분탐색을 사용한 방법과, bisect 라이브러리를 사용한 방법. 

 

1. nlist라는 빈 배열을 선언하고, 입력받은 수열의 값들을 차례대로 넣을지 말지 결정한다. nlist의 인덱스값을 mid로 설정한다. for문은 수열 A의 index값을 초기화하고 증가시킨다. 그래서 해당 index보다 입력받은 수열 A의 값과 비교한다. 수열 A의 값이 nlist의 mid보다 크다면, low 값을 1씩 증가시켜간다. 그리고 이 low를 가지고 nlist에 추가(append)를 할지, 덮어쓸지를 결정한다.

 

2. 이번에는 bisect이라는 라이브러리를 사용할 것이다. bisect 라이브러리의 기본 컨셉은 정렬된 리스트를 삽입 후에 다 시 정렬할 필요 없도록 관리할 수 있도록 지원하는 것이다. 기본적인 이진 분할 알고리즘을 사용하기 때문에 bisect이라고 부른다. bisect, bisect_right, bisect_left, insort, insort_right, insort_left가 있는데, 우리는 bisect_left를 사용할 것이다.  주어진 값 x와 같은 값이 리스트 내에 있을 때, x의 위치가 동일한 값으로부터 왼쪽에 있을지 오른쪽에 있을지를 결정하는 기준이 된다. bisect_left는 x와 동일한 값이 리스트에 있을 시, 왼쪽에 삽입 시키겠다는 것이다.

bisect_left 함수

 

---

코드

from sys import stdin

var_N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))
nlist = [0]
                                # A = [10,20,10,30,20,50]
for a in range(var_N):          # a = 0    1         2       3            4 5
    low = 0                     # l = 0 1  0 1 2     0 0 1   0 1 2 3      ...
    high = len(nlist) - 1       # h = 0 0  1 1 1     2 0 0   2 2 2 2      ...
    while low <= high:          # m = 0    0 1       1 0     1 1 2        ...
        mid = (low +high)//2
        if nlist[mid] < A[a]:
            low = mid + 1
        elif nlist[mid] >= A[a]:
            high = mid - 1
    if low >= len(nlist):       # 1>=1     2>=2              3>=3         ...
        nlist.append(A[a])      # [0,10]   [0,10,20]         [0,10,20,30] ...
    elif low < len(nlist):      #                    1<3                  ...
        nlist[low] = A[a]       #                    10=10                ...

print(len(nlist) - 1)

from sys import stdin
from bisect import bisect_left

var_N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))
nlist = [0]

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

print(len(nlist)-1)

---

마무리

bisect 라이브러리만 알고 있다면, 그리고 이분탐색이라는 것을 충분히 익혀온 지금이라면, 쉽게 풀 수 있다.