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

문제 링크

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

문제

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

알고리즘: 이분 탐색, 그리디

풀이

주어진 수열을 for문으로 실행한다.
주어진 수열의 수를 n이라고 하고 현재 증가하는 수열을 담은 list를 sn이라고 하겠다.
n이 sn의 마지막 값보다 크다면 끝에 삽입해준다.
그렇지 않다면 n은 sn의 마지막 값보다 같거나 작은 값이다.
이분 탐색을 이용해서 sn의 n이 어느 자리에 들어갈 수 있는지 탐색한다.
들어갈 위치를 찾았다면 그 위치에 n값으로 대체한다.
해당 위치보다 n 값이 더 작은 값이기 때문에 새로 추가된 n 앞에 더 많은 수를 넣을 수 있다.
ex) 1 2 10 보다 1 2 4는 5~9까지의 값을 더 넣을 수 있음.
for 문이 끝나면 sn의 size를 출력한다.

소스 코드

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

public class Main {
    static int N;
    static ArrayList<Integer> sn_list = new ArrayList<>();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            int n = Integer.parseInt(st.nextToken());
            if(sn_list.size()==0) {
                sn_list.add(n);
            } else {
                if(sn_list.get(sn_list.size()-1) < n) sn_list.add(n);
                else {
                    int j = binary_search(n);
                    sn_list.set(j, n);
                }
            }
        }
        System.out.println(sn_list.size());
    }
    static int binary_search(int target) {
        int left = 0;
        int right = sn_list.size() -1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(sn_list.get(mid) == target) return mid;
            else if(sn_list.get(mid) > target) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
}