[백준] 12015번 가장 긴 증가하는 부분 수열 2 (Python 파이썬)

www.acmicpc.net/problem/12015

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

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다.

예를 들어, A = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이다.

 

---

풀이 과정

먼저, 풀이과정 두가지를 이용할 수 있는데,

하나는 이진탐색을 직접 구현하여 수열이 들어갈 자리를 찾는 방법이고

다른 하나는 내장 모듈인 bisect를 이용한 방법이다.

 

먼저 풀이1번 부터 설명하자면,

array는 문제에서 설명한 수열A를 나타낸다. A에 수열의 모든 원소들을 저장한다.

stack은 정답을 나타낼 가장 긴 증가하는 부분수열을 나타낼 것이다.

 

for문 부분부터 살펴보면, 수열A를 처음부터 돌면서 수열들을 뽑아내게 되는데

현재 원소가 stack의 마지막 원소보다 크다면, 당연히 수열을 연장할 수 있으므로 stack의 마지막에 추가한다.

하지만 그렇지 않다면? 버려야 할까?

그렇지 않다.

만약, 현재 stack이 10, 20, 40, 60으로 구성되어 있고, 현재 50이 들어갈 자리가 60이 있는 자리인 상황이라면

60을 50으로 교체해야 더 긴 수열을 연장할 수 있다.

왜냐하면, 10, 20, 40, 60 일때 55가 들어온다면 연장할 수 없지만 10, 20, 40, 50 일 경우에는 연장할 수 있기 때문이다.

그래서, else문에 stack[binary_search(i, 0, len(stack) - 1)] = i 라는 조건을 준 것이다.

n = int(input())
array = list(map(int, input().split()))
stack = [0]


def binary_search(target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if stack[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start


for i in array:
    if stack[-1] < i:
        stack.append(i)
    else:
        stack[binary_search(i, 0, len(stack) - 1)] = i

print(len(stack) - 1)

 

다른 풀이과정은 간단하다, 

bisect_left는 리스트에서 i라는 원소가 들어갈 가장 왼쪽 위치를 반환해주는 함수이다.

위 방법과 마찬가지로 stack의 가장 마지막 원소가 현재 진입하려는 원소보다 작으면 뒤로 이어서 붙여주면 되고,

아닌 경우에는 이진탐색을 통해 해당 인덱스의 원소를 교체해주면 된다.

from bisect import bisect_left

n = int(input())
array = list(map(int, input().split()))
stack = [0]

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

print(len(stack)-1)

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !