[알고리즘-자바] 백준 14002번 가장 긴 증가하는 부분 수열 4

본 글은 다크모드에 최적화되어 있습니다.

문제

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

14002번: 가장 긴 증가하는 부분 수열 4

언어

자바 Java

해설

이 문제는 최장 증가 수열(Longest Increasing Subsequence)를 사용하여 해결할 수 있습니다. LIS에 대한 내용은 여기를 참고해주세요.

 

위 문제와 크게 다른 점은 없으나, LIS를 갖는 숫자의 리스트를 추가적으로 출력하는 조건이 붙었습니다. LIS를 구할 당시에 숫자 리스트를 저장하지 않고, 마지막이 되어서야 숫자 리스트를 구하려면 어떻게 해야 할까요? 숫자들이 담겨있는 리스트를 마지막 인덱스부터 순회를 돌며 추적을 해야 합니다. 왜냐하면 LIS값이 클수록, 해당 LIS를 갖는 숫자는 뒤쪽에 위치하게 되기 때문입니다.

Stack<Integer> st = new Stack<>();
for (int i = n; i >= 1; i--) {
    if (dp[i] == max) {
        st.push(nums[i - 1]);
        max--;
    }
}

마지막 인덱스부터 추적을 하기 앞서, Stack을 왜 사용할까요? Stack은 LIFO(Last In First Out) 구조를 갖습니다. 즉, 마지막으로 추가한 값을 가장 먼저 꺼내는 구조입니다. LIS를 갖는 부분 수열은 오름차순으로 정렬되어 있기 때문에, 큰 값을 먼저 넣고 작은 값은 마지막에 스택에 저장해야 합니다.

 

dp에는 숫자 리스트의 각 인덱스에 해당하는 LIS값이 저장되어 있습니다. dp[i] == max(여기서 max는 최대 LIS)가 성립하면 스택에 해당 숫자를 저장하고 max를 1 줄여줍니다. 왜냐하면 현재 숫자보다 앞에 있는 숫자들은 현재 LIS보다 반드시 1 이상 작아야 하기 때문입니다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];
        int[] nums = new int[n];
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++)
            nums[i] = Integer.parseInt(input[i]);

        for (int i = 1; i <= n; i++) {
            dp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (nums[i - 1] > nums[j - 1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int max = 0;
        for (int i = 1; i <= n; i++)
            max = Math.max(max, dp[i]);
        sb.append(max + "\n");

        Stack<Integer> st = new Stack<>();
        for (int i = n; i >= 1; i--) {
            if (dp[i] == max) {
                st.push(nums[i - 1]);
                max--;
            }
        }

        while (!st.isEmpty())
            sb.append(st.pop() + " ");
        System.out.println(sb);
    }
}

 

---

PS

역추적에 대한 설명이 좀 복잡한데... 직접 코딩해 보면서 천천히 생각해 보시면 이해가 될 거라 생각합니다.