[백준] 14003. 가장 긴 증가하는 부분 수열 5 (Java)

 

문제

14003번: 가장 긴 증가하는 부분 수열 5

 

알고리즘

이분 탐색

 

풀이

가장 긴 증가하는 부분 수열 3 문제와 동일하지만 LIS 수열까지 출력해줘야하는 문제이다.

이분 탐색을 이용한 방식은 LIS의 길이는 보장하지만 LIS 수열은 보장하지 않았다.

 

LIS 수열을 구하기 위해 수열의 각 원소가 리스트의 어느 위치에 들어갔었는지 기록하고,

수열의 뒤에서부터 역추적하여 해결하였다.

 

[2 4 1 8 7 5 9 0 3 6] 의 수열로 표를 그리면 다음과 같다.

수열과 list에 삽입된 위치

list의 크기, 즉 lis의 길이가 4이므로

index 배열의 뒤에서부터 3~0까지 값을 가진 첫 숫자들이 LIS 를 이루는 수임을 알 수 있다.

 

뒤에서부터 탐색하므로 스택을 이용해 꺼내며 출력하였다.

 

* 앞에서부터 0~3을 탐색하면 올바른 LIS를 찾지 못한다.

 

 

코드

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

public class Main {
	static ArrayList<Integer> list;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		list = new ArrayList<>();

		int N = Integer.parseInt(br.readLine());
		int[] indexArr = new int[N];
		int[] arr = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());
			arr[i] = num;

			if (i == 0 || list.get(list.size() - 1) < num) {
				list.add(num);
				indexArr[i] = list.size() - 1;
			} else {
				int index = lowerBound(num);
				list.set(index, num);
				indexArr[i] = index;
			}
		}

		Stack<Integer> stack = new Stack<>();
		
		int index = list.size() - 1;
		for (int j = N - 1; j >= 0; j--) {
			if (indexArr[j] == index) {
				stack.push(arr[j]);
				index--;
			}
		}
		
		sb.append(list.size()).append("\n");
		while(!stack.isEmpty())
			sb.append(stack.pop()).append(" ");
		System.out.println(sb);
	}

	static int lowerBound(int num) {

		int left = 0;
		int right = list.size();

		while (left < right) {
			int mid = (left + right) / 2;

			if (list.get(mid) < num)
				left = mid + 1;
			else
				right = mid;
		}

		return right;
	}
}