[KOITP] 최장 증가 부분 수열(LIS) 2

출    처 : http://koitp.org/problem/LIS2/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	512 MB	1513	306 (20%)	255

문제

부분 수열(Subsequence)은 어떤 수열에서 순서를 유지하되, 그 중 일부 항만을 선택하여 만들 수 있는 수열이다. 예를 들어, $[1,3,2,4]$로 이루어진 수열이 있다면, $[1,3,4]$, $[1,2,4]$등은 부분 수열이 될 수 있지만, $[1,2,3]$은 부분수열이 될 수 없다.

최장 증가 부분 수열(Longest Increasing Subsequence)은 어떤 수열의 부분 수열 중 각 항이 이전 항에 비해 증가하는 부분 수열을 의미한다. 예를 들어, 수열 $[1,8,4,12,2,14,6]$의 최장 증가 부분 수열은 $[1,8,12,14]$, $[1,4,12,14]$가 있다.

수열이 주어졌을 때, 해당 수열의 최장 증가 부분 수열의 길이를 알아내자.

입력

첫 번째 줄에 수열의 길이 $N$이 주어진다. ($1\le N\le 300,000$)

두 번째 줄에 수열의 각 항의 값이 순서대로 주어진다. 주어지는 숫자는 32비트 정수형 이내의 숫자이다.

출력

첫 번째 줄에 주어진 수열의 최장 증가 부분 수열의 길이를 출력한다.

힌트

예제 입력

10
1 1 2 2 3 3 2 2 5 5

예제 출력

4

< Comment >

 발상 자체는 간단합니다.

 최장 증가 수열일 경우, 앞에서부터 탐색한다면 당연히 큰 값보다 작은값이 LIS에 포함되어 있을 경우에 더 유리합니다. 그렇기 때문에, N-1까지 인덱스를 증가시키면서 만약 자신보다 큰 값이 LIS 안에 존재한다면, 해당 값보다 LIS의 숫자가 커지는 경우를 현재 값으로 대체합니다.

 이를 끝까지 진행하면, 결국 이 값이 LIS가 결과로 출력됩니다. 처음에 코드를 짤 때는, 아무 생각없이 LIS 배열의 처음부터 끝까지 루프를 돌렸었는데, 이와같이 풀 경우에는 타임아웃이 발생해, binarySearch 로 대체하였습니다.

 Arrays.binarySearch() 의 경우, 만약 값이 없을 경우에 "자신이 해당 배열 안에 위치한다면" 가질 (인덱스 + 1) 값에 마이너스를 붙여 리턴값을 돌려줍니다. 물론 값이 있을 경우에는 그대로 index를 출력해 줍니다. 아무튼 음수가 출력될 경우가, 저희가 필요한 경우이므로, 큰값을 자신으로 바꾸기 위해, 여기에 다시 Array 인덱스에 맞도록 1을 더해주고 양수로 바꿔주어 LIS값을 변경하는 식으로 진행합니다.

 그리고 마지막 값보다 클 경우, LIS의 길이 값을 증가시키며 LIS 마지막에 숫자를 붙여줍니다.

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

public class LIS2 {
	
	public static int N = 0;	// [1, 300000]
	public static int dp[] = null;
	
	public static int arr[] = null;
	public static int LIS[] = null;
	
	public static int INF = Integer.MAX_VALUE;

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		LIS = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0 ; i < N ; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.fill(LIS, INF);
		int len = 1;
		LIS[0] = arr[0];
		for (int i = 1 ; i < N ; i++) {
			
			if (LIS[len - 1] < arr[i]) {
				LIS[len++] = arr[i];
				continue;
			}
			
			int idx = Arrays.binarySearch(LIS, arr[i]);
			if (idx < 0) {
				idx = -(idx + 1);
				LIS[idx] = arr[i];
			} 
		}
		
		bw.write("" + len);
		bw.flush();
		bw.close();

	}
}