[Python_Search] 백준 12015번 : 가장 긴 증가하는 부분 수열 2

1. 문제

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

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

 

 

 

2. 풀이과정

입력된 값을 하나씩 읽어가면서, 결과 배열에 들어갈 위치를 이진탐색을 통해 찾는다.

#입력 : 10 20 15 30 70 50
10
10 20
10 15
10 15 30
10 15 30 70
10 15 30 50

 

결과 배열의 마지막 값보다 크면 제일 뒤에 추가하고, 아니면 자기보다 작은 값들의 뒷자리를 차지하도록 만든다.

 

 

방법 1) 이진탐색 구현

import sys
input = sys.stdin.readline

n = int(input())
result = [0]

def find(su):
  start = 0
  end = len(result) - 1

  while start <= end:
    mid = (start+end)//2

    if result[mid] < su:
      start = mid+1
    else:
      end = mid-1
  return start

for a in list(map(int, input().split())):
  if result[-1] < a:
    result.append(a)
  else:
    result[find(a)] = a

print(len(result)-1)

 

 

방법 2) 라이브러리 활용

bisect_left : 왼쪽 인덱스 반환

bisect_right : 오른쪽 인덱스 반환

#bisect 라이브러리 설명
arr = [1, 2, 3, 3, 3, 4, 5]
bisect_left(arr, 3) #2
bisect_right(arr, 3) #5

from bisect import bisect_left

n = int(input())
result = [0]

for a in list(map(int, input().split())):
  if result[-1] < a:
    result.append(a)
  else:
    result[bisect_left(result, a)] = a

print(len(result)-1)