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

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

난이도 : 플래 5

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

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

 

전략

수열의 크기 N이 최대 1,000,000이므로 O(N^2) 알고리즘으로는 해결할 수 없다.

이를 O(NlogN)만에 해결할 수 있는 LIS 알고리즘은 이분 탐색과 메모이제이션을 함께 사용한다.

 

1. dp[len]은 길이가 len인 증가하는 부분 수열 중에서 가장 작은 마지막 원소가 저장된다.

2. 주어진 수열을 순차적으로 탐색한다. 이를 seq[i]라고 하면

2-a. dp[len] < seq[i]

: dp[++len]에 seq[i]를 기록한다.

2-b. dp[len] >= seq[i]

: dp[x] < seq[i]를 만족하는 dp[x] 중 가장 큰 x 위치를 이분 탐색으로 구해서 seq[i]를 저장한다.

 

시행착오

LIS 길이가 아닌 값을 얻기 위해서 dp가 교체될 때마다 값을 저장하고, LIS를 만족하는 조건 내에서 가장 작은 것부터 선택해서 출력했다.

(역추적을 하면 훨씬 효율적으로 풀 수 있다.)

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

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[] seq = new int[N];
        int[] dp = new int[N+1];
        ArrayList<Integer>[] save = new ArrayList[N+1];

        // init
        for (int i=0; i<=N; i++) {
            dp[i] = Integer.MIN_VALUE;
            save[i] = new ArrayList<>();
        }

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

        int len = 0;
        for (int i=0; i<N; i++) {
            if (seq[i] > dp[len]) {
                len += 1;
                dp[len] = seq[i];
                save[len].add(i);
            } else {
                int idx = binSearch(dp, 0, len, seq[i]);
                dp[idx] = seq[i];
                save[idx].add(i);
            }
        }

        System.out.println(len);
        int[] ans = new int[N+1];
        int prev = Integer.MAX_VALUE;

        for (int i=N; i>0; i--) {
            Collections.sort(save[i]);
            for (int idx : save[i]) {
                if (idx < prev) {
                    if ((prev < Integer.MAX_VALUE && seq[idx] < seq[prev]) || prev == Integer.MAX_VALUE) {

                        ans[i] = seq[idx];
                        prev = idx;
                        break;
                    }
                }
            }
        }

        for (int i=1; i<=len; i++) {
            System.out.print(ans[i] + " ");
        }

    }

    static int binSearch(int[] arr, int left, int right, int find) {
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] < find)
                left = mid + 1;
            else
                right = mid;
        }
        return right;
    }
}

 

깨달은 점

LIS가 아직 익숙하지 않아서 코드가 깔끔하지 않다.

dp 배열의 경우 ArrayList 등의 자료구조를 활용한다면 len을 따로 관리하지 않아도 된다.

단순히 LIS 길이만 구하는 것이 아니라 역추적이 필요한 문제인데 정석이 아닌 트릭으로 풀어서 공간 낭비가 있다.

역추적에 대한 연습이 더 필요할 것 같다.