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

www.acmicpc.net/problem/14003

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

 

1. 문제 설명

 

수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 구하고 가장 긴 증가하는 부분 수열을 출력하는 문제이다.

 

 

2. 풀이

 

가장 긴 증가하는 부분 수열을 푸는 방법에는 여러 가지가 있는데 DP를 이용한 방법과 이분 탐색을 이용한 방법이 있다.

DP를 이용하는 방법의 경우 O(N^2)의 시간 복잡도가 걸리고 이분 탐색의 경우 O(NlogN)의 시간 복잡도를 가진다.

 

이 문제의 경우 수열 A의 크기가 최대 10^6이 때문에 DP를 이용해서 풀게 되면 시간제한에 걸리게 된다.

 

따라서 이분탐색을 이용한 방법으로 풀어야 한다.

 

이분 탐색에 사용할 배열 B를 하나 생성한 후 배열 A에서 list [x] 이상이 처음 나오는 위치를 찾고 그 위치에 list [x]를 저장한다.

 

이 방법은 주의해야할 점이 있는데 이분 탐색의 결과를 저장하는 배열 B가 수열 A의 가장 긴 증가하는 부분 수열이 아니라는 사실이다.

 

예를 들어 수열 A가 { 10 20 10 30 20 15}라고 하자.

 

이분 탐색을 통해서 배열 B를 채워나가면 아래와 같은 값으로 채워질 것이다.

 

10

15

30

이 결과는 수열 A의 가장 긴 증가하는 부분 수열일 수 없다. 실제 수열 A의 순서와 다르기 때문이다.

 

실제로 예시의 배열 B에서 수열 A의 마지막 값 15가 30 앞에 있는 것을 볼 수 있다.

 

그렇기에 이분 탐색을 저장하는 배열 외에도 역추적을 위한 배열을 하나 더 만들어야 한다.

 

아래 코드는

 

dp [][0]은 이분 탐색을 이용하여 수열의 수를 저장하였고

dp [][1]은 현재 dp 위치에 저장되는 list 인덱스를 저장하였다.

그리고 dp[][1]을 바탕으로 trace 배열에 이전의 선택 인덱스를 저장하였다.

 

추적을 하기 위해 dp [][1]에 현재 인덱스를 저장하고 trace 배열에 이전 선택의 인덱스를 저장하여 이를 역추적하였는데

 

이런 식으로 하는 것보다 list의 현재 위치의 최장 부분 수열의 길이를 저장하는 인덱스 배열을 하나 생성하고 역추적하는 게 공간적으로 좋은 방법인 거 같다.

 

 

3. 코드

import java.io.*;
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 num=Integer.parseInt(br.readLine());

        int[] list=new int[num+1];
        int[][] dp=new int[num+1][2];
        int[] trace=new int[num+1];

        int start=0,end=0;

        StringTokenizer st=new StringTokenizer(br.readLine());

        dp[0][0]=-1000000001;
        dp[0][1]=-1;

        for(int x=1;x<=num;x++){
            list[x] = Integer.parseInt(st.nextToken());

            int n_start=start;
            int n_end=end;

            while(n_start<n_end){
                int middle=(n_start+n_end)/2;

                if(dp[middle][0]>=list[x])
                    n_end=middle;
                else
                    n_start=middle+1;
            }

            if(end==n_end && dp[end][0]<list[x]){
                end++;
                n_end++;
            }

            dp[n_end][0]=list[x];
            dp[n_end][1]=x;
            trace[x]=dp[n_end-1][1];
        }


        bw.write(String.valueOf(end)+"\n");

        int last=dp[end][1];

        int [] answer=new int[end];

        for(int x=end-1;x>=0;x--){
            answer[x]=list[last];
            last=trace[last];
        }

        for(int x=0;x<end;x++){
            bw.write(String.valueOf(answer[x]+" "));
        }

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

        br.close();
    }


}