[BaekJoon] 12738 가장 긴 증가하는 부분 수열 3 (Java)

1.  문제 링크

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

2.  문제

요약

• 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 수열 A의 크기 N이 주어지고 두 번째 줄에 -1,000,000,000보다 크거나 같고 1,000,000,000보다 작거나 같은 수열 A를 이루고 있는 $A_i$가 주어집니다.
• 출력: 첫 번째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력합니다.

3.  소스코드

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

public class Main {
    static int N;
    static int[] sequence;

    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        sequence = new int[N];

        for(int idx = 0; idx < N; idx++)
            sequence[idx] = scanner.nextInt();
    }

    static void solution() {
        ArrayList<Integer> subsequence = new ArrayList<>();
        subsequence.add(0);
        for(int idx = 0; idx < N; idx++) {
            if(sequence[idx] > subsequence.get(subsequence.size() - 1)) {
                subsequence.add(sequence[idx]);
            } else {
                int index = binarySearch(1, subsequence.size() - 1, sequence[idx], subsequence);
                subsequence.set(index, sequence[idx]);
            }
        }
        System.out.println(subsequence.size() - 1 == 0 ? 1 : subsequence.size() - 1);
    }

    static int binarySearch(int left, int right, int objective, ArrayList<Integer> subsequence) {
        while(left < right) {
            int mid = (left + right) / 2;
            if(subsequence.get(mid) < objective) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 가장 긴 증가하는 부분 수열의 수들을 넣을 subsequence라는 ArrayList를 생성하고 0을 넣어 초기화합니다.
• 수열의 첫 번째 수부터 마지막 수까지 확인하면서 가장 긴 증가하는 부분 수열의 길이를 구합니다.
  • 만약 subsequence의 마지막 수가 수열의 현재 수보다 작다면 subsequence에 수열의 현재 수를 추가합니다.
  • 그렇지 않다면 이분탐색을 통해 subsequence에서 적절한 위치를 찾아 subsequence의 찾은 위치의 수를 수열의 현재 수로 변경합니다.
    • 수를 변경하는 이유는 수열에 있는 수 중에서 subsequence에 들어가있는 수보다 더 작은 수들 중에 가장 긴 증가하는 부분 수열에 들어가는 수들이 있을 수 있기 때문에 이를 넣기 위함입니다.
• 위 과정을 모두 끝낸 후의 (subsequence의 길이 - 1)의 값이 가장 긴 증가하는 부분 수열의 길이가 됩니다. 만약 이 값이 0이 된다면, 가장 긴 증가하는 부분 수열의 길이는 최솟값인 1이 됩니다.