[백준] 2352 반도체 설계 (JAVA)

풀이

LIS문제를 더풀어보고 DP문제를 더 풀어보자고 생각을해 문제들을 찾아보다가 이문제를 발견하였고 처음보았을때는 LIS를 그냥 적용하면 될것 같아 쉽네~ 이러고 했는데 시간초과까지는 아니지만 너무 오래 걸려서 풀렸다. 그래서 다른 방법이 있나 하고 찾아 보았고 해답은 바이너리 서치와 LIS 를 섞어서 푸는 것이였다. 기존의 LIS방식은 시간복잡도가 O(N*N)이였는데 이번에 풀은 방식의 시간복잡도는 O(NlogN)이다.

전체적인 큰틀은 다음과 같다.

 

1. 배열탐색하면서 가장큰수를 계속 뒤에 이어붙인다

2. 중간에 끼어들수 있는수는 이분탐색을 이용해, 적절한 위치에 있던 수와 교체한다.

3. 배열을 탐색하면서 맨앞요소보다 작은 요소가 새익면 맨앞요소를 교체한다.

 

처음에는 두번째와 세번째가 이해가 잘 되지 않을수 있는데 쉽게 생각하면 기존의 LIS는 각 위치에서의 LIS를 모두 구했는데 이분 탐색은 모든위치가 아니라 그냥 제일 증가하는 길이가 큰 것만 찾는것이라고 생각하면 될것 같다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), "");

        int n = Integer.parseInt(st.nextToken());
        int [] arr = new int[n];
        int [] lis = new int[n];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        lis[0] = arr[0];
        int idx = 1; // lis배열의 길이
        int temp = 0;

        for(int i=0; i<n; i++){
            if(lis[idx-1] < arr[i]){ // 가장 큰 수 -> 이어 붙인다.
                lis[idx++] = arr[i];
            }else if(lis[0] > arr[i]){ // lis의 처음 수보다 작은 값을 교체
                lis[0] = arr[i];
            }
            else{
                temp = Arrays.binarySearch(lis, 0 , idx, arr[i]);
                lis[temp < 0 ? (-temp - 1) : temp] = arr[i];
            }
        }

        System.out.println(idx);
    }

}