[BOJ] 14002. 가장 긴 증가하는 부분수열4

LIS 알고리즘 - 이진탐색(NlogN)

• 메모리 : 13,340 KB
• 시간 : 88 ms
• 코드길이 1,562 B
• 소요시간 : 45M
• 이진 탐색에서 같은 숫자를 찾을 경우 그 자리의 index를 주기때문에 temp값에 음수가 나와서 처음에 런타임 에러가 떳었다. 그래서 음수값이 나오는 경우는 이미 배열에 있기 때문에 패스하는 if (temp < 0) continue;를 추가해주었더니 통과할 수 있었다.

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

public class Main_B_14002_가장긴증가하는부분수열4_이진탐색 {

	static int N, num[];
	static StringBuilder answer = new StringBuilder();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		num = new int[N];
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		for (int i = 0; i < N; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		lisPath();
		System.out.println(answer);
		in.close();
	}

	private static void lisPath() {
		int[] lis = new int[N];
		int[] lisIndex = new int[N];
		int[] preIndex = new int[N];
		int size = 0, temp = 0;

		for (int i = 0; i < N; ++i) {
			temp = -(Arrays.binarySearch(lis, 0, size, num[i])) - 1;
			if (temp < 0) continue; // 같은 숫자를 찾을 경우는 패스
			lis[temp] = num[i];
			lisIndex[temp] = i;
			// 자신의 위치가 0(첫번째)이면 이전은 없고, 자신의 위치가 0이 아니라면 현재 lis 구성의 바로 직전이 이전됨.
			preIndex[i] = (temp == 0) ? -1 : lisIndex[temp - 1];

			if (temp == size)
				++size;
		}
		answer.append(size).append('\n');
		// 경로 출력을 위한 코드
		int cur = lisIndex[size - 1];
		Stack<Integer> stack = new Stack<Integer>();
		while (cur != -1) {
			stack.push(num[cur]);
			cur = preIndex[cur];
		}
		while (!stack.isEmpty()) {
			answer.append(stack.pop()).append(' ');
		}
	}
}

LIS 알고리즘 - DP

• 메모리 : 13,656 KB
• 시간 : 100 ms
• 코드길이 : 1,400 B
• 소요시간 : 15M

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

public class Main_B_14002_가장긴증가하는부분수열4_DP {

	static int N, num[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		num = new int[N];
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		for (int i = 0; i < N; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		} // end input
		lisPath();
	} // end main

	private static void lisPath() {
		StringBuilder answer = new StringBuilder();
		int lis[] = new int[N]; // 길이를 담을 배열
		int pre[] = new int[N]; // 경로를 추척할 인덱스를 담을 배열
		int maxIndex = 0;
		for (int i = 0; i < N; ++i) {
			lis[i] = 1;
			pre[i] = -1;
			for (int j = 0; j < i; ++j) {
				if (num[i] > num[j] && lis[i] < lis[j] + 1) {
					lis[i] = lis[j] + 1;
					pre[i] = j;
					if (lis[maxIndex] < lis[i])
						maxIndex = i;
				}
			}
		}
		answer.append(lis[maxIndex]).append('\n');

		int cur = maxIndex;
		Stack<Integer> stack = new Stack<Integer>();
		while (cur != -1) {
			stack.push(num[cur]);
			cur = pre[cur];
		}
		while (!stack.isEmpty()) {
			answer.append(stack.pop()).append(' ');
		}
		System.out.println(answer);
	} // end listPath

}