자바 - 백준 12015 / 가장 긴 증가하는 부분 수열2

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

12015번: 가장 긴 증가하는 부분 수열 2

골드2

 

구현 방법

수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이므로 DP로 풀 경우  O(n^2)의 시간복잡도를 가지므로 런타임 에러가 발생한다. 따라서 이 문제의 경우, 이분 탐색으로 구현해야 한다. 하지만 여기서 이해가 안되는 부분이 생겼다.

예를 들어서 5 6 2 7이라는 수열이 있다고 하자. 이 경우 이분 탐색으로 구현 하면 순서는 다음과 같다.

1. 5

2. 5 6

3. 2 6

4. 2 6 7 

이렇게 된다. 하지만 LIS(최장 증가 부분 수열)은 실제로 5 6 7이 맞다.(왜냐하면 순서가 존재하므로) 그래서 알아보니 이 경우는 단순히 LIS의 길이만 구하기 때문에 위와 같이 구현해도 되는 거였다.

따라서 실제 LIS를 구하기 위해서는 순서 인덱스를 저장하는 배열을 하나더 만들어서 저장해 줘야 한다.

 

그외 구현과정에서 고려해야 할 부분은 값을 추가하는 것이 아니고 "대치" 해야 한다는 점이다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.*;

/**
 * 백준 12015
 * 가장 긴 증가하는 부분 수열2
 * 골드2
 * https://www.acmicpc.net/problem/12015
 */
public class b12015 {

	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[] ary = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++)
			ary[i] = Integer.parseInt(st.nextToken());
		
		List<Integer> lis = new ArrayList<>();
		 
		lis.add(ary[0]);
		for(int i = 1; i < n; i++) {
			if(lis.get(lis.size() - 1) < ary[i])
				lis.add(ary[i]);
			else {
				int start = 0;
				int end = lis.size() - 1;
				
				//이분 탐색
				while(start < end) {
					int mid = (start + end) / 2;
					
					if(ary[i] <= lis.get(mid)) {
						end = mid;
					} else if(ary[i] > lis.get(mid)) {
						start = mid + 1;
					} 
				}
				//값이 같지 않다면 대치
				if(lis.get(start) != ary[i])
					lis.set(start, ary[i]);
			}
		}
		
		System.out.println(lis.size());
	}
}

느낀 점

DP를 사용하면 무조건 시간 복잡도가 줄어들거라고 생각했는데 이 문제를 통해 그렇지 않다는 점을 알게 되었다.

 

참고 블로그

https://kimmessi.tistory.com/191

[알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력