[백준, python] 12015번 - 가장 긴 증가하는 부분 수열 2

백준 문제풀이 시작

---

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

풀이

풀이 확인하기

이 문제는 백준 11053번과 동일한 문제로 보이지만 똑같이 코드를 짤 경우 시간 초과가 뜰 것이다. 그래서 시간을 줄일 수 있는 방법을 생각해야 한다. 기존 문제를 푸는 과정에서 매번 max 함수를 통해 값을 비교하는 과정에서 모든 뒤 숫자들을 비교하게 된다. 이는 비효율적이므로 이분 탐색을 통해 해당 수가 뒤 어디에 들어올만한지 효율적으로 찾을 수 있다. 위치를 찾은 뒤 해당 수와 수를 교체하는 과정으로 코드를 수정해주면 O(NlogN) 시간으로 문제를 해결할 수 있다.
(P.S. 해당 코드의 ans는 실제 lis가 아니다.)

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

f = int(input())
line = list(map(int, input().strip().split()))
ans = []
lens = 1

ans.append(line[0])
for i in range(1, len(line)):
    if(ans[lens-1] < line[i]):
        ans.append(line[i])
        lens += 1
    else:
        j = bisect_left(ans, line[i])
        ans[j] = line[i]

print(lens)

• baekjoon
• python