[SWEA] 3307. 최장 증가 부분 수열

LIS DP방법

• 메모리 : 28,152 KB
• 실행시간 : 152 ms
• 코드길이 : 1,150 B
• 소요시간 : 10M
• 이제야 원리를 완전히 이해했다. 제일 아래의 코드보다 이 코드가 더욱 이해하기에 도움이 되는 것 같다. NlogN방법이 기억이 안날때는 이 코드는 작성할 수 있을 것 같다.

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

public class Solution_D3_3307_최장증가부분수열_LIS_DP {

	static int N, num[], lis[];

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

			// LIS DP방법
			int maxIndex = 0;
			for (int i = 0; i < N; i++) {
				lis[i] = 1; // lis배열 초기화
				for (int j = 0; j < i; j++) {
					if (num[i] > num[j] && lis[i] < lis[j] + 1) {
						lis[i] = lis[j] + 1;
						if (lis[maxIndex] < lis[i])
							maxIndex = i;
					}
				}
			}
			answer.append('#').append(tc).append(' ').append(lis[maxIndex]).append('\n');
		} // end test-case;
		System.out.print(answer);
		in.close();
	} // end main
}

LIS 이진탐색 방법 (NlogN)

• 메모리 : 21,576 KB
• 실행시간 : 127 ms
• 코드길이 : 1,074 B
• 소요시간 : 10M
• 경로를 출력하는 코드는 아니고 길이만 구하는 코드!

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

public class Solution_D3_3307_최장증가부분수열_LIS_NlogN {

	static int N, num[], lis[];

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

			// LIS 이진탐색방법
			int size = 0, temp;
			for (int i = 0; i < N; i++) {
				temp = -(Arrays.binarySearch(lis, 0, size, num[i])) - 1;
				lis[temp] = num[i];
				if (temp == size)
					++size;
			}
			answer.append('#').append(tc).append(' ').append(size).append('\n');
		} // end test-case;
		System.out.print(answer);
		in.close();
	}

}

LIS_NlogN 방법

• 메모리 : 21,180 KB
• 실행시간 : 129 ms
• 코드길이 : 1,656 B
• 소요시간 : 20 M
• 위와 같은 코드이지만 위 코드가 나한테는 더 이해가 쉽다.

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

public class Solution_D3_3307_최장증가부분수열 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder answer = new StringBuilder();
		int T = Integer.parseInt(in.readLine());
		for (int tc = 0; tc < T; tc++) {
			answer.append('#').append(tc + 1).append(' ');
			int N = Integer.parseInt(in.readLine());
			int[] numbers = new int[N];
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			for (int i = 0; i < N; i++) {
				numbers[i] = Integer.parseInt(st.nextToken());
			} // end input

			int[] C = new int[N];
			int[] path = new int[N];
			int size = 0;

			path[size] = -1;
			C[size++] = 0;
			for (int i = 1; i < N; i++) {
				if (numbers[C[size - 1]] < numbers[i]) {
					path[i] = C[size - 1];
					C[size++] = i;
				} else {
					int temp = binarySearch0(numbers, C, 0, size, numbers[i]);
					if (temp < 0)
						temp = -temp - 1;
					path[i] = path[C[temp]];
					C[temp] = i;
				}
			}

			answer.append(size).append('\n');
		} // end test case

		System.out.println(answer);
		in.close();
	} // end main

	private static int binarySearch0(int[] numbers, int[] c, int fromIndex, int toIndex, int key) {
		int low = fromIndex;
		int high = toIndex - 1;

		while (low <= high) {
			int mid = (low + high) >>> 1;
					int midVal = numbers[c[mid]];

					if (midVal < key)
						low = mid + 1;
					else if (midVal > key)
						high = mid - 1;
					else
						return mid;
		}
		return -(low + 1);
	}

}