[백준 14002] 가장 긴 증가하는 부분 수열4

문제

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

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

풀이

이 문제는 수열이 주어질 때 가장 긴 증가하는 부분수열의 길이와 요소들을 순차적으로 출력하는 문제이다. LIS와 Stack의 개념을 적용해 풀이해보자.

LIS(Longest Increasing Subsequence)

LIS의 약어를 해석해보면 최장 증가 부분 수열이다. 이것은 문제가 요구하는 수열을 의미하는 용어임을 알 수 있다.

 

LIS를 구현하는 방법은 크게 DP를 이용한 방법과 이분 탐색(Binary Search)를 이용한 방법이 있다. DP의 구현할 경우 O(n^2)의 시간복잡도를 갖지만, 이분 탐색의 경우 O(n log n)의 시간 복잡도를 갖는다. 이 문제의 경우 DP로 분류가 되어 있기 때문에 DP를 활용해 풀이했다.

 

DP를 사용한 풀이는 이중 for문을 사용해 구현한다.

 

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

 

j는 i만큼, 즉 현재 인덱스 위치의 바로 이전 위치까지의 요소 값을 비교한다. 이렇게 비교를 하면서 현재의 값이 더 크다면, dp[i]의 위치에 dp[j] + 1의 값을 저장한다. max 변수에 최대 값을 갱신한다.

 

arr = {10, 30, 20, 50, 30, 20}
dp = {1, 2, 2, 3, 0, 0}

 

예를들어 i가 50의 위치에 있을 경우를 설명해본다면, j는 50이전의 요소들을 순차적으로 순회하며 i의 값을 비교한다. 앞의 모든 요소보다 현재의 값(50)이 크기 때문에 if문의 조건을 통과하게 되고, dp[i]의 값은 비교하며 높은 값만 가질 수 있도록 유지된다.

 

이렇게 구했다면 max의 값으로 LIS의 길이를 구할 수 있다.

 

 

Stack

문제는 최장 길이만 출력하는 것이 아닌 요소까지의 출력을 원한다. 출력은 길이만 맞다면 어떤 요소가 출력되어도 인정이 된다고 명시되어 있다.

 

출력을 위해선 어떻게 해야 할까?

 

Stack을 사용해 오름차순으로 출력을 구현할 수 있다. Stack은 LIFO(Last In First Out)의 특징을 갖는다. 이 특징과 최대 길이를 이용해서 순차적인 출력을 구현하는 것이다.

 

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

while (!nums.empty()) {
    bw.write(nums.pop() + " ");
}

 

dp 배열을 뒤에서부터 순회한다. for문이 처음 시작될 때 max의 값과 일치하는 dp[i]가 있다면 그 값은 dp에서 가장 큰 수일 것이다. 그렇다면 수열에서의 i 인덱스에 해당하는 값 또한 가장 큰 수를 의미하는 것이라고 볼 수 있다. 그리고 수열에서 꺼낸 값을 Stack에 넣고 max의 값을 하나씩 줄여가며 탐색한다.

 

이렇게 되면 오름차순에 맞는 값들을 순서대로 구할 수 있다. 하지만 뒤에서부터 탐색하기 때문에 순서가 반대가 된다. 이 문제를 해결하기 위해 Stack이 사용된다. Stack의 LIFO 특징을 이용하면 빼내면서 순차적으로 쉽게 오름차순으로 출력을 할 수 있다.

코드

package 가장긴증가하는부분수열4;

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        br.close();

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

        bw.write(max + "\\n");

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

        while (!nums.empty()) {
            bw.write(nums.pop() + " ");
        }

        bw.flush();
        bw.close();
    }
}