[Java] 백준 12015 가장 긴 증가하는 부분 수열 2 (G2)

문제 해결 전략

이 문제는 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다.

dp를 이용하여 모든 요소를 비교하면서 가장 긴 증가하는 부분 수열을 찾을 수도 있지만, 이는 시간복잡도가 O(n^2)로 수열의 길이가 1,000,000이기 때문에 timeout이 날 것이다.

 

이 문제를 풀 때는 길이를 강조하고 싶었다.

 

주어진 수열을 모두 순환하면서 만나는 값이 현재 가장 긴 증가하는 수열의 max value보다 크다면 append하고 그렇지 않다면 수열 중 가장 가장 가까우면서 크지 않은 값으로 교체하는 방법을 사용했다.

가장 가까우면서 크지 않은 값으로 교체하는 이유는 뒤에 올 수 있는 수의 범위를 넓혀주기 위해서다.

 

 

예를 들어 특정 수열을 기반으로 가장 긴 증가하는 부분 수열을 만들어간다고 가정하자. 빨간색 부분이 새로 읽어들이는 숫자이고, 그 숫자를 어디에 위치시킬 것인지 구하는 알고리즘을 그림으로 그리면 다음과 같다.

 

다음 예시로 조금 더 복잡한 수열을 보자, 이 수열은 중간 번호를 교체하는 로직이 들어가 있다.

 

주의 할 점은 최종적으로 만들어지는 수열이 가장 긴 증가하는 부분 수열이 아니라는 점이다.

그와 길이는 같지만, 그 수열이라고는 할 수 없다.

전체 코드

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

public class BOJ_12015 {

    private static int input;
    private static int[] arr;
    private static int[] targetArr;

    public static void main(String[] args) {
        initialize();
        solve();
    }

    private static void solve() {
        targetArr = new int[input];
        int currentIndex = 0;
        targetArr[currentIndex] = arr[0];

        for (int i = 1; i < input; i++) {
            int currentTarget = arr[i];

                        // 새로 읽어들이는 수가 가장 크다면 그냥 append한다.
            if (targetArr[currentIndex] < currentTarget) {
                targetArr[++currentIndex] = currentTarget;
                continue;
            }

            int first = 0;
            int last = currentIndex;

                        // 새로 읽어들이는 수가 가장 크지 않다면 교체하기 위한 자리를 이분탐색으로 찾는다.
            while (first < last) {
                int mid = (first + last) / 2;
                if (targetArr[mid] < currentTarget) {
                    first = mid + 1;
                    continue;
                }
                last = mid;
            }
            targetArr[first] = currentTarget;
        }

        System.out.println(currentIndex + 1);
    }

    private static void initialize() {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            input = Integer.parseInt(br.readLine());
            arr = new int[input];
            initializeArray(br);
        } catch (IOException e) {
            throw new IllegalArgumentException(e);
        }
    }

    private static void initializeArray(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < input; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    }
}

느낀점

이번 문제를 풀면서 가장 이해하기 어려웠던 점은 가장 긴 증가하는 부분 수열의 길이 / 가장 긴 증가하는 부분 수열 을 구분하는 것이였다.

dp를 이용하면 그 길이를 직관적으로 풀어낼 수 있었을 것이지만, 시간복잡도를 조금이라도 줄여야지 이 문제를 통과할 수 있다.

문제를 보고 해결책이 바로 생각나지는 않았다. 수열과 논리에 대해서 더욱 공부해야겠다.

 

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