백준 14003번: 가장 긴 증가하는 부분 수열 5

문제

수열 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,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

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

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

 

• 알고리즘: LIS (Longest Increasing Subsequence)
• 접근 방식: 시간 초과 때문에 DP 사용 불가 → 이진 탐색을 활용한 O(N log N) 방식
• 포인트: LIS의 길이 뿐 아니라 실제 수열을 추적하여 출력하는 방식

 

O(N²) 방식 vs O(N log N) 방식 비교

• O(N²)은 dp[i]를 이용해 이전 값을 전부 탐색하며 길이를 구함 → 시간 초과
• O(N log N)은 이진 탐색을 이용해 적절한 위치에 값을 덮어쓰며 LIS 길이만 유지
  → 실제 수열은 바로 알 수 없기 때문에 **추적용 배열(prev)과 인덱스 리스트(index)**를 별도로 사용함

예시

8
10 20 10 30 20 25 50 7

list 변화:
[10]
[10, 20]
[10, 20]
[10, 20, 30]
[10, 20, 30]
[10, 20, 25]
[10, 20, 25, 50]
[7, 20, 25, 50] ← 덮어쓰기지만 LIS 길이는 유지됨

• index는 각 자리의 실제 인덱스를 저장 → 역추적 시작 인덱스를 index.get(list.size() - 1)로 바로 구할 수 있음
• prev[i]는 arr[i] 앞에 있던 LIS 구성 요소의 인덱스를 저장
• 마지막 인덱스부터 prev를 따라가며 Stack에 담은 후 출력

 

자바 코드

 

○ list

LIS 길이계산용

 

○  index

list에서 각 위치에 어떤 인덱스의 값이 들어왔는지 기록

 

○  prev

arr[i] 앞에 어떤 인덱스가 LIS 경로에 있었는지를 기록 (역추적용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] prev = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            prev[i] = -1;
        }

        List<Integer> list = new ArrayList<>();
        List<Integer> index  = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int idx = binarySearch(list, arr[i]);

            if (idx == list.size()) {
                list.add(arr[i]);
                index.add(i);
            } else {
                list.set(idx, arr[i]);
                index.set(idx, i);
            }

            if (idx > 0) prev[i] = index.get(idx - 1);
        }

        int lastIndex = index.get(list.size() - 1);
        Stack<Integer> stack = new Stack<>();
        while (lastIndex != -1) {
            stack.push(arr[lastIndex]);
            lastIndex = prev[lastIndex];
        }

        System.out.println(stack.size());
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }

    public static int binarySearch(List<Integer> list, int target) {
        int left = 0;
        int right = list.size();

        while (left < right) {
            int mid = (left + right) / 2;

            if (list.get(mid) >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

 

시간 복잡도

• LIS 길이 계산: O(N log N) 이진탐색 (binarySearch)
• 역추적: O(N) (한 번 따라가면서 Stack에 담음)

→ 시간 복잡도: O(N log N)