[BOJ] 14003 가장 긴 증가하는 부분 수열 5

date

Aug 5, 2023

slug

boj-14003

author

status

Public

문제 링크

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

문제

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

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

문제풀이

가장 긴 증가하는 부분 수열 3의 nlogn과

가장 긴 증가하는 부분 수열 4의 N의 역추적을 합친 문제이다.

nlogn 알고리즘을 통한 길이를 구할때

추가 배열 arr_total을 선언해주어

arr에 들어가는 위치인 idx와

삽입할 값 value를 tuple로 저장해준다.

그럼 tuple로 저장한 (value, idx)가 N만큼있을텐데

뒤부터 돌면서 idx가 arr의 길이 일때부터 1일때까지 하나씩 빼주면서

스택에 넣어주고 뒤집어서 출력해주면 된다.

파이썬 문제풀이 코드


import bisect
N = int(input())

arr = []
arr_total = [] 
for idx, item in enumerate(map(int, input().split())):
    if not arr:
        arr.append(item)
        arr_total.append((item, 1))
    
    elif arr:
        if arr[-1] < item:
            arr.append(item)
            arr_total.append((item, len(arr)))
        else:
            idx = bisect.bisect_left(arr, item) # 어디들어갈 수 있는지 찾는다
            arr[idx] = item
            arr_total.append((item, idx+1))
        
print(len(arr))
max_len = len(arr)
arr2 = []
# print(arr_total )
for item in arr_total[::-1]:
    value, idx = item
    if idx == max_len:
        max_len -= 1
        arr2.append(value)
        
print(*arr2[::-1])

시간복잡도

O(nlogn)

입력

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

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

출력

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

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

예제 입력


6
10 20 10 30 20 50

예제 출력


4
10 20 30 50

알고리즘 분류

구현

문자열