[백준 12015 : JAVA] 가장 긴 증가하는 부분 수열 2 / 이진탐색 풀이

개요

 

이 문제는 [최장 증가수열] LIS (Longest Increasing Subsequence)로 유명한 문제인 것 같다.

이 문제는 두 번째 버전의 문제로 [11053 가장 긴 증가하는 수열 1] 문제가 첫 번째 버전의 문제라고 생각할 수 있다. 

첫 번째 버전을 풀지 않았다면 풀고 오는것을 추천한다.  ▶ https://www.acmicpc.net/problem/11053

기존의 첫 번째 버전과 차이점은 입력되는 값의 범위이다.

첫 번째 버전보다 입력되는 값의 범위가 1,000 -> 1,000,000으로 변경되었기 때문에 

기존의 동적 프로그래밍 방식으로 풀게 되면 O(N^2)이 되어 시간 초과가 나게 된다.

우리는 이분 탐색을 이용하여 O(NlogN)의 시간 복잡도로 풀게 될 것이다.

 

문제 

 

수열 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)

 

 

 

풀이

 

• 리스트를 이용하여 풀이한다. -> 어떤 자료구조를 사용해도 무방하다.
• 입력될 수 있는 값들보다 무조건 작은 수인 0을 미리 넣어둔다. (첫 번째 입력받은 수가 비교를 할 수 있도록)
• 입력을 받을 때는 두 가지 경우가 존재한다. 
  
  1.  이전에 입력받은 값 보다 큰 수를 입력받은 경우
     • 리스트에 입력 받은 값을 추가한다. (결국에는 오름차순의 조합을 만드는 것이기 때문이다.)
  2.  이전에 입력받은 값 보다 작거나 같은 수를 입력받은 경우
     • 리스트를 오름차순이라 생각하고, 이분 탐색을 통해 입력받은 값이 들어갈 자리를 찾는다.
     • 찾은 자리에 삽입이 아닌 기존의 값을 입력받은 값으로 변경한다.
• 리스트의 사이즈 - 1을 출력한다. (처음에 넣은 0을 세지 않기 위한 작업이다.)

 

◆  처음에 이해가 잘 안되어 입력받을 때 리스트에 값이 변하는 것을 확인하니 이해가 되었다.

 

10 입력 ▶ [0 10]   →  입력된 값이 0번 인덱스보다 크기 때문에 추가한다.

20 입력 ▶ [0 10 20]  → 입력된 값이 1번 인덱스보다 크기 때문에 추가한다.

10 입력 ▶ [0 10 20]  → 입력된 값이 2번 인덱스보다 작기 때문에 이분 탐색을 통해 적합한 자리를 찾고 값을 변경한다.

30 입력 ▶ [0 10 20 30]  → 입력된 값이 2번 인덱스보다 크기 때문에 추가한다.

20 입력 ▶ [0 10 20 30]  → 입력된 값이 3번 인덱스보다 작기 때문에 이분탐색을 통해 적합한 자리를 찾는다.

50 입력 ▶ [0 10 20 30 50]  -------------> 답 : 리스트 사이즈 - 1 : 4

 

◆  문제에서 주어진 입력 값으로는 정확히 어떻게 변하는지 쉽게 파악하기 어렵다.

◆  6 

◆  10 20 1 2 3 4 

◆  를 입력 받았다고 생각해보겠다.

 

 

10 입력 ▶ [0 10] 

20 입력 ▶ [0 10 20]

 1 입력 ▶ [0  1 20]

 2 입력 ▶ [0  1  2]  → 현재까지 입력받은 결과로는 [10 20] , [1 2] 두 개의 조합이 존재한다.

                               [10 20]을 덮어 써도 되는 이유는 [1 2] 의 경우는 앞으로 [10 20] 뒤에 나올 경우를

                               포괄하고 있기 때문이다.

 3 입력 ▶ [0  1  2  3]

 4 입력 ▶ [0  1  2  3  4]  -------------> 답 : 리스트 사이즈 - 1 : 4

 

 

코드

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

public class Backjoon12015 {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        List<Integer> list = new ArrayList<>();
        list.add(0);

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

        for(int i = 0 ; i < n; i++) {
            int value = arr[i] = Integer.parseInt(st.nextToken());
            if(value > list.get(list.size() - 1)) list.add(value);
            else{
                int left = 0;
                int right = list.size() - 1;

                while(left < right){
                    int mid = (left + right) >> 1;
                    if(list.get(mid) >= value){
                        right = mid;
                    }else{
                        left = mid + 1;
                    }
                }
                list.set(right, value);
            }
        }
        System.out.println(list.size() - 1);
    }

}

 

 

■ 이해가 되지 않을 떄는 내가 생각한 예시 입력을 머리와 손으로 그려보면 왜 이러한 방식으로 코드를 짜게 됐는지 알 수 있는 것 같다.