[12015 - JAVA] 가장 긴 증가하는 부분 수열 2

 

문제

 

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

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

입력

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

제출

 

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

class Main {
    static int a;
    static int[] a_list, LIS;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        a = Integer.parseInt(br.readLine());

        a_list = new int[a];
        LIS = new int[a];

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

        LIS[0] = a_list[0];
        int length = 1;

        for (int i = 1; i < a; i++) {
            int key = a_list[i];

            if (LIS[length - 1] < key) {
                length++;
                LIS[length - 1] = key;
            }
            else {
                int low = 0;
                int high = length;
                while (low < high) {
                    int mid = (low + high) / 2;

                    if (LIS[mid] < key) {
                        low = mid + 1;
                    }
                    else {
                        high = mid;
                    }
                }
                LIS[low] = key;
            }
        }

        System.out.println(length);
        
    }
}

 

처음 문제를 봤을 때는 이분 탐색이라는 알고리즘 유형을 확인하지 않았으면 무슨 알고리즘으로 풀어야되는지에 대한 감도 잡히지 않았다. 인터넷에 풀이를 보고 문제가 이해가 된 뒤에야 풀 수 있던 문제였다. 

 

문제에서 증가하는 수열의 크기를 구하는 문제여서 단순히 완전 탐색을 이용하면 풀 수 는 있지만 시간이 매우 오래걸리는 문제가 있다 분명 시간초과에 걸릴 것이다. 풀이에서는 단순히 수열의 크기 증가를 구하는 것에 초점을 맞추지 않고 길이를 구하는 방식으로 답을 구했다. 

 

입력 받은 배열 값이 0 index 값을 기준으로 LIS 추가된 이전 값과의 크기를 비교하고 작고 크고에 따라 기존 값에 "추가"가 아닌 "대치"하는 방식으로 값을 갱신해 답을 구한다.

 

해당 방식을 이용해 값을 구하면 LIS 값은 정확한 수열 증가 값에 해당하지 않더라도 길이는 동일하게 구할 수 있다.

 

10, 20, 10, 30, 15, 40, 50

 

정석 수열 증가 값 = 10 20 30 40 50

해당 문제 결과 = 10 15 30 40 50

 

하지만 결과적으로 동일한 길이를 구할 수 있다.