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

개요

 

이 문제는 2가지 정도의 풀이가 존재한다.

1. 동적 프로그래밍 

2. 이분 탐색

 

하지만, 이 문제의 입력에서 n의 값이 1,000,000 이기 때문에 이분 탐색으로 풀이하여야 시간 초과를 피할 수 있다.

 

간단히 설명하자면 우리가 구하고자 하는 증가 수열을 List 자료구조에 저장하고

새로 들어온 값에 대해서 list 안에서의 위치를 찾아 list를 갱신해주는 것이다.

 

문제

 

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

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

 

입력

 

풀이

 

개요에서 말했듯이 이분탐색을 이용해서 수열의 적당한 위치를 찾아 줄 것이다.

 

입력된 값의 처음부터 순차적으로 검사를 시작한다. 검사를 할 때 아래와 같이 2가지 경우로 나뉘게 된다.

 

- 검사하는 숫자가 증가수열 리스트의 마지막 숫자보다 큰 경우

   → 증가수열 리스트에 추가한다.

- 검사하는 숫자가 증가수열 리스트의 마지막 숫자보다 작은 경우 

   → 증가수열 리스트내의 적당한 위치를 찾아서 갱신한다.

 

예제 입력과 같이 입력이 들어왔을 때의 시퀀스는 아래와 같다. (증가수열 리스트이다.)

 

 

위와 같이 시퀀스가 나타나고 최종적으로 list길이를 이용하여 정답을 도출해 낼 수 있다.

단, list에 저장된 숫자들이 실제 증가 수열이 되는 것은 아니다.

그 이유는 10 20 30 14 24 50 과 같은 입력을 해보며 손으로 그려보면 알 수 있다.

만약 실제 증가수열의 값들을 구하고 싶다면 아마도 역추적을 통해 구할 수 있을 것이다.

 

 

코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
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];

        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);
            // 확인하는 숫자가 증가수열의 마지막 수보다 작은 경우
            else{
                // 숫자의 적당한 위치를 찾아
                // 증가수열의 값을 변경해준다.
                while(left < right){
                    int mid = (left + right) >> 1;

                    if(list.get(mid) >= num) right = mid;
                    else left = mid + 1;
                }
                list.set(right, num);
            }
        }
        // 최장 길이 출력
        sb.append(list.size() - 1 + "\n");

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