[백준] 12015번 - 가장 긴 증가하는 부분 수열 2 (이분 탐색) - 결과 포함

www.acmicpc.net/problem/12015

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

증가하는 수열의 길이를 구하는 문제이다.

입력의 크기가 100만이기 때문에 수열을 완전 탐색하면서 길이를 셀 수 없다.

 

이번 문제를 해결하면서 밑에 블로그를 참고했다.

[참고]suri78.tistory.com/199

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

쉬워보였지만 생각보다 어려운 문제였다.

일단 경우의 수를 생각했다.

주어지는 수열은 정렬되지 않고 작은 값이 앞에 올지 큰 값이 앞에 올지 알지 못한다.

그렇기 때문에 주어지는 수열의 값들을 차례대로 확인해야 하는 것은 맞다.

 

수열의 값들을 확인할 때마다 새로운 리스트에 추가해주면 정렬된 상태의 증가하는 부분 수열을 만들 수 있을 것이다.

수열을 만들 때 중요한 것은 들어가는 숫자의 위치이다.

처음에는 바로 삽입하면 되지만 이후에는 이미 수열에 존재하는 값들에 따라서 위치를 찾아야 한다.

 

1. 새로운 리스트를 만들 때 비교를 위해서 "0" 값을 삽입한다.

 

2. 가장 큰 수가 들어오는 경우와 아닌 경우로 조건을 나누어서 처리한다.

 

3. 위치를 빠르게 찾기 위해서 이분 탐색을 사용한다.

 

입력 받은 수열을 차례대로 확인하면서 현재 새롭게 만든 리스트의 마지막 값과 비교한다.

항상 가장 큰 값을 마지막 자리에 삽입했기 때문에 만약 리스트의 마지막 값보다 크다면 현재까지의 부분 수열에서 가장 크다는 것을 의미한다. 결과적으로 맨 뒤에 바로 삽입하면 된다.

 

문제는 중간에 들어가야 하는 값이 들어오는 경우다.

문제의 조건이 증가하는 부분 수열이기 때문에 수열의 값들은 바로 앞에 값보다 무조건 커야한다.

이를 지키기 위해서 들어갈 인덱스를 찾아야 한다.

 

순차 탐색은 시간이 오래 걸리기 때문에 이분 탐색을 사용한다.

새로 만든 부분 수열의 길이만큼 이분 탐색을 수행하면서 중간값과 찾으려는 값을 비교하여 알맞은 위치를 찾는다.

 

그러나 여기서 문제가 발생한다.

맨 뒤에 append 하는 것이 아니라 중간에 들어 가는 것이라면 이미 그 배열의 인덱스에는 다른 값이 존재할 수 있다.

이분 탐색을 수행할 때 조건은 자신의 앞에 있는 값보다 크면 되기 때문에

예를 들어

현재 [ 10, 20, 30, 40 ] 이렇게 수열이 있고

20보다 큰 25가 들어오려 한다면 30을 지우고 [ 10, 20, 25, 40 ] 이런 결과가 나타난다.

 

엄밀히 말하면 25는 입력 받은 수열에서 다른 숫자들보다 뒤에 있었으므로 비집고 들어올 수 없다.

하지만 이 문제는 수열 자체를 출력하는 것이 아니라 가장 긴 부분 수열의 길이를 구하는 문제이다.

문제가 없는 이유는 가장 큰 값이 아닌 이상 기존의 수열에서 뒤에 있는 숫자들이 새로운 수열의 앞부분으로 올 수는 없기 때문이다.

 

[소스 코드]

import sys

n = int(sys.stdin.readline().rstrip())
data = list(map(int, sys.stdin.readline().rstrip().split()))

arr = [0]


def binary_search(start, end, target):
    while start < end:
        mid = (start + end) // 2
        if arr[mid] < target:
            start = mid + 1
        elif arr[mid] > target:
            end = mid
        else:
            end = start = mid
    return end


for num in data:
    if num > arr[-1]:
        arr.append(num)
    else:
        start = 1
        end = len(arr) - 1
        idx = binary_search(start, end, num)
        arr[idx] = num

print(len(arr) - 1)