[백준 14003: JAVA] 가장 긴 증가하는 부분 수열 5/ 이분 탐색+ 역추적

개요

 

이 문제는 이분 탐색으로 풀이할 수 있다. (dp로는 입력의 최댓값이 너무 커서 시간 초과가 날 것이다.)

시간은 O(nlog(n))이 될 것이다.

사실 이 문제는 기존의 아래 문제에서 경로의 개념만 추가된 것이다.

그러므로 아래의 문제를 먼저 풀어 보는 것을 추천한다.

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

12738번: 가장 긴 증가하는 부분 수열 3

위 문제에서 공통으로 적용되는 이분탐색을 통해 증가수열의 길이를 구하는 것은 아래의 풀이에서 설명이 되어 있으니 참고하면 좋을 것 같다.

 

2020/02/20 - [알고리즘/백준] - [백준 12738: JAVA] 가장 긴 증가하는 부분 수열 3/ 이분 탐색

[백준 12738: JAVA] 가장 긴 증가하는 부분 수열 3/ 이분 탐색

 

 

문제

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

풀이

 

주어진 수열이 {1, 5, 6, 2, 3, 4} 라고 한다면

리스트와 index배열에는 다음과 같이 값이 저장될 것이다.

이 이유를 모른다면 개요에 나와있는 다른 포스팅을 참고하고 오길 바란다.

 

위와 같이 indexArr이 저장되면

최장길이인 4를 기준으로 시작하여 역추적을 하게 된다.

이때 편리성을 위해서 stack자료구조에 값을 저장하였다.

또한 뒤에서부터 검사를 하는 이유는 나중에 선택된 놈이 최후의 선택이 되기 때문이다.(단 예외가 있지만 기준 값이 있기 때문에 반례가 나오지는 않는다.)

 

코드

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

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 이분탐색을 통해 증가하는 수열을 저장할 객체
        List<Integer> list = new ArrayList<>();
        // 입력된 수열을 저장
        int arr[] = new int[n + 1];
        // 입력된 각 수열의 위치를 저장
        int indexArr[] = new int[n + 1];

        // 수열을 입력받아 저장한다.
        for(int i = 1 ; i <= n; i++) arr[i] = Integer.parseInt(st.nextToken());

        list.add(Integer.MIN_VALUE);

        for(int i = 1 ; i <= n; i++){
            int num = arr[i];
            int left = 1;
            int right = list.size() - 1;

            // 확인하는 숫자가 수열의 마지막 수보다 큰 경우
            // 수열에 추가해준다.
            if(num > list.get(list.size() - 1)) {
                list.add(num);
                indexArr[i] = list.size() - 1;
            }
            // 확인하는 숫자가 수열의 마지막 수보다 작은 경우
            else{
                while(left < right){
                    int mid = (left + right) >> 1;

                    if(list.get(mid) >= num) right = mid;
                    else left = mid + 1;
                }
                list.set(right, num);
                indexArr[i] = right;
            }
        }
        // 최장 길이 출력
        sb.append(list.size() - 1 + "\n");
        // 역추적 경로를 저장할 stack
        Stack<Integer> stack = new Stack();

        // 현재 찾길 원하는 증가수열의 인덱스 값
        int index = list.size() - 1;

        for(int i = n; i > 0; i--){
            // 찾길 원하는 인덱스와 같은 경우
            if(indexArr[i] == index){
                // 찾길 원하는 인덱스를 하나 감소시킨다.
                // 다음 인덱스의 값을 찾기 위해서
                index--;
                // stack에 경로를 추가한다.
                stack.push(arr[i]);
            }
        }

        // 스택에서 꺼내며 찾는다.
        while (!stack.isEmpty()){
            sb.append(stack.pop() + " ");
        }

        bw.write(sb.toString());
        bw.close();
        br.close();
    }
}