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

문제

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

 

풀이

해당 문제는 LIS 풀이로 접근했습니다.
하지만, 가장 긴 증가하는 부분 수열 시리즈 1번보다 입력 값이 큰 점에서 차이가 있습니다.(N 최대 1,000,000)
이 부분을 이분탐색을 적용하여 시간 복잡도를 줄였습니다.



풀이 방법은 다음과 같습니다.
1. 가장 긴 증가하는 부분수열이 담길 list를 선언 및 초기화합니다.(초기 값으로 list에 0을 add 해줍니다. list size를 체크할 때 에러방지)

 

2. 입력값을 하나씩 받으며 로직을 진행합니다.(로직은 list 값을 변경하거나 추가하기 위해 진행합니다.)

 

2-1. tgt(입력받은 값)이 list의 마지막 인덱스에 위치한 값보다 클 경우, (마지막에 추가해도 증가 수열이 유지되기 때문에) list에 해당 값을 add합니다.

 

2-2. 2-1 케이스가 아닌 경우, 이분탐색을 진행합니다. mid 값이 tgt보다 작을 경우 left를 mid+1 값으로 변경하고 이외의 경우는 right = mid로 변경해줍니다. 이분탐색이 끝나면 list의 right 인덱스 위치의 값을 tgt로 대체합니다.

3. list size의 -1 값(초기에 0추가한 것을 길이에서 빼주기)을 리턴합니다.

 

코드

117,716 KB / 680 ms

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

public class Main {
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        list.add(0);

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

        for(int i = 0 ; i < N ; i ++)
            bs(Integer.parseInt(st.nextToken()));

        System.out.println(list.size() - 1);
    }

    private static void bs(int tgt) {
        if(tgt > list.get(list.size() - 1)) list.add(tgt);
        else{
            int left = 0;
            int right = list.size() - 1;

            while(right > left){
                int mid = (left + right) / 2;

                if(list.get(mid) < tgt) left = mid + 1;
                else right = mid;
            }

            list.set(right, tgt);
        }
    }
}