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

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

 

문제 탐색하기

주어진 N 길이의 수열에서 제일 긴 증가하는 수열을 찾아내는 문제이다. 입력의 개수가 훨씬 더 작았다면 O(N^2)시간에도 찾을 수 있지만 N의 최대가 100만 인 만큼 O(N^2) 시간안에 풀 수 없다. 따라서 다른 방법을 통해 정답을 찾아야 한다. 

 

완전 탐색을 하지 않더라도 여전히 N만큼의 탐색시간을 거쳐야 한다. 어떤 방법으로 이걸 찾을 수 있을까? 리스트를 하나 두고 해당 연결리스트에 값을 추가하거나 새로 수정하여 구하는 방법을 통해서 O(Nlog(N)) 시간 안에 답을 찾을 수 있다.

 

다음은 문제에서 나온 예제이다. 이를 통해서 어떤 방식으로 O(Nlog(N)) 시간 안에 답을 찾을 수 있는지 알아보자.

6
10 20 10 30 20 50

 

먼저 리스트에 맨 처음 숫자를 더한다.

[10]

 

그 다음 숫자부터 이분 탐색을 통해서 위 리스트에서 어떤 인덱스에 추가되어야 할지 결정하면 된다.

예를 들어서 20을 이분탐색을 통해서 위 리스트에 추가하고자 하면 리스트의 길이인 1에 추가해야한다고 나올 것이다. 이에 따라서 리스트의 길이에다가 추가하려고 하면 리스트의 맨 뒤에 추가해주고 그 외의 경우는 기존 리스트 값을 대체 하면 된다. 

 

위의 예시를 계속 이어서 설명해보면

2) 20은 기존 리스트의 뒤에 추가하면 된다 (이분 탐색 결과가 1)

[10, 20]

3) 10은 기존 리스트의 0에 추가하라고 나올 것이다. 이에 따라서 기존 리스트의 10을 다시 10으로 대체한다.

[10, 20]

4) 30은 기존 리스트의 뒤에 추가하면 된다. (이분 탐색 결과가 2)

[10, 20, 30]

5) 앞서 10의 경우와 마찬가지로 이분 탐색 결과가 1이 나오기 때문에 기존 리스트의 20을 20으로 대체한다.

[10, 20, 30]

6) 50은 기존 리스트의 뒤에 추가하면 된다. (이분 탐색 결과가 3)

[10, 20, 30, 50]

 

코드 설계하기

1. 입력을 처리하고 배열에 모든 숫자를 담는다.

2. 0번째 수를 리스트에 더한다. 반복 문을 통해서 1번째부터 n - 1번 째 수 까지의 위치를 이분 탐색으로 결정한다.

3. 이분 탐색 결과에 따라서 리스트를 수정한다.

4. 리스트의 길이를 출력한다.

 

시도 회차 수정 사항

1회차

이분 탐색 이후 low랑 high를 조절하는 것을 잘못 생각해서 수정하였다. Java에서 리스트의 특정 위치에 원소를 더하는 연산과 리스트 모든 요소를 지우는 연산이 시간이 O(N) 걸리는 부분을 놓쳐서 시간 초과를 받았다. 이를 기존 위치의 원소를 수정하는 것으로 바꾸어 연산의 시간 복잡도를 낮췄다.

 

풀이

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

public class Main {
    static class FastReader {
		BufferedReader br;
		StringTokenizer st;
 
		public FastReader() {
			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());
		}
	}
    
    public static void main(String[] args) {
        FastReader fr = new FastReader();
        int N = fr.nextInt();
        int[] arr = new int[N];
        
        for (int i = 0; i < N; i++) {
            arr[i] = fr.nextInt();
        }
        
        int result = 0;
        List<Integer> list = new ArrayList<>();
        list.add(arr[0]);
        for (int i = 1; i < N; i++) {
            int low = 0;
            int high = list.size();
            int target = 0;
            while (low < high) {
                target = (low + high) / 2;
                if (list.get(target) < arr[i]) {
                    low = target + 1;
                } else {
                    high = target;
                }
            }
            if (high == list.size()) {
                list.add(arr[i]);
            } else {
                list.set(high, arr[i]);
            }
        }
        System.out.println(list.size());
    }
}