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

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

예전에 가장 긴 증가하는 부분 수열 문제를 풀었었는데 이번에는 다른 점이 메모리 부분이 다

---

문제

 

코드

import sys
input = sys.stdin.readline

n = int(input())
cases = list(map(int, input().split()))
lis = [0]

for case in cases:
    if lis[-1] < case:
        lis.append(case)
    else:
        left = 0
        right = len(lis)

        while left < right:
            mid = (right + left) // 2
            if lis[mid] < case:
                left = mid + 1
            else:
                right = mid

        lis[right] = case

print(len(lis) - 1)

 

 

설명

이진 탐색을 사용하여 효율적으로 위치를 찾는게 목표입니다

수열의 각 원소 case에 대해 lis 리스트에서 적절한 위치를 찾아 삽입하거나 대체하는 코드 입니다

 

• 큰 값은 단순 추가: 현재 수열의 값이 lis의 마지막 값보다 크면 lis에 그대로 추가합니다.
• 작거나 같은 값은 대체: 그렇지 않으면 이진 탐색을 통해 lis에서 적절한 위치를 찾아 해당 위치의 값을 현재 값으로 대체합니다. 이를 통해 lis는 항상 증가하는 부분 수열의 값을 유지하게 됩니다.

 

 

예시

예를 들어, 수열이 10 20 10 30 20 50인 경우를 살펴봅시다:

 

• 초기 상태: lis = [0]
• 첫 번째 원소 10 처리: lis = [0, 10] (10을 추가)
• 두 번째 원소 20 처리: lis = [0, 10, 20] (20을 추가)
• 세 번째 원소 10 처리: lis = [0, 10, 20] (이진 탐색을 수행하여 위치를 찾습니다)
• 네 번째 원소 30 처리: lis = [0, 10, 20, 30] (30을 추가)
• 다섯 번째 원소 20 처리: lis = [0, 10, 20, 30]
• 여섯 번째 원소 50 처리: lis = [0, 10, 20, 30, 50] (50을 추가)

 

최종적으로 lis 리스트는 [0, 10, 20, 30, 50]이 됩니다. 여기서 초기값 0을 제외한 부분 수열의 길이는 4입니다. 따라서 가장 긴 증가하는 부분 수열의 길이는 4가 됩니다.

 

초기값 0은 처음 if문에서 동작하기 위함입니다