[JAVA] BOJ 백준 14003번 - 가장 긴 증가하는 부분 수열 5

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

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

---

2. 내가 푼 방법

DP와 이분 탐색을 함께 사용해 풀었다.

 

우선 int[][] valueDP 배열은 가장 큰 수열 값이 들어가며 valueDP 값이 현재 값(arr[i])보다 더 클 경우 업데이트되며, 증가하는 부분 수열의 가장 긴 길이를 구하는 용도이다. int[][] indexDP 배열은 valueDP 배열에서 값이 업데이트될 때, 업데이트되는 인덱스 값을 저장해둔다. 추후 증가하는 부분 수열을 출력할 때 사용된다.

 

이제 for문을 돌면서 binarySearch 함수를 통해 현재 값이 valueDP에 저장된 값보다 더 큰 값을 가지는 인덱스를 가져온다. (이로 인해 나올 수 있는 값의 범위가 (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 이므로 valueDP를 -1,000,000,001로 초기화한 것이다.) 

탐색 후 -1을 반환하면, 다음에 올 수열에 저장될 수 있는 것이므로 valueDP[lis]에 현재 값을 저장하고 lis++;를 해준다. 또는 인덱스를 반환하면, valueDP[idx]를 더 작은 값으로 업데이트해 주면서 indexDP에 각각 인덱스도 저장해둔다.

 

나머지는 indexDP를 통해 lis-1과 같은 값을 가지는 인덱스를 저장한 수열을 스택에 넣어주면 된다. lis-- 되면서 마지막은 -1이 나오기 때문에, indexDP를 -1로 초기화한 것이다.

public static void solution() {
    int lis = 0;
    Arrays.fill(indexDP, -2);
    Arrays.fill(valueDP, -1000000001);

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

        if (idx == -1) {
            valueDP[lis] = arr[i];
            indexDP[i] = lis++;
        }
        else {
            valueDP[idx] = arr[i];
            indexDP[i] = idx;
        }
    }

    for (int i = N-1; i >= 0; i--) {
        if (lis - 1 == indexDP[i]) {
            stack.add(arr[i]);
            lis--;
        }
    }
}

public static int binarySearch(int s, int e, int target) {
    int res = -1;

    while (s <= e) {
        int mid = (s + e) / 2;

        if (target <= valueDP[mid]) {
            res = mid;
            e = mid - 1;
        }
        else {
            s = mid + 1;
        }
    }

    return res;
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B14003.java

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static int[] arr, indexDP, valueDP;
    static Stack<Integer> stack;

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        int lis = 0;
        Arrays.fill(indexDP, -2);
        Arrays.fill(valueDP, -1000000001);

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

            if (idx == -1) {
                valueDP[lis] = arr[i];
                indexDP[i] = lis++;
            }
            else {
                valueDP[idx] = arr[i];
                indexDP[i] = idx;
            }
        }

        for (int i = N-1; i >= 0; i--) {
            if (lis - 1 == indexDP[i]) {
                stack.add(arr[i]);
                lis--;
            }
        }
    }

    public static int binarySearch(int s, int e, int target) {
        int res = -1;

        while (s <= e) {
            int mid = (s + e) / 2;

            if (target <= valueDP[mid]) {
                res = mid;
                e = mid - 1;
            }
            else {
                s = mid + 1;
            }
        }

        return res;
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(stack.size()+"\n");

        while (!stack.isEmpty()) {
            bw.write(stack.pop()+" ");
        }

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

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        indexDP = new int[N];
        valueDP = new int[N];
        stack = new Stack<>();

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

        br.close();
    }
}

---

4. 결과 및 회고

어쩌면 LIS 알고리즘은 완벽하게 이해한걸지도? ㅎㅎ