[14003] 가장 긴 증가하는 부분 수열 5 - Java[자바]

 

 

드디어 LIS의 끝인 가장 긴 증가하는 부분 수열 5문제로 왔습니다.

 

 

 

| 문제 링크

 

 

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

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

 

 

 

 

 

---

 

 

 

 

 

| 문제

 

1. 크기가 N인 수열이 주어집니다. (1 ≤ N ≤ 1,000,000)
2. 가장 긴 증가하는 부분 수열의 길이와 해당하는 부분 수열을 출력하시오.

 

 

 

 

 

---

 

 

 

 

 

| 풀이

 

1. 수열의 값을 입력 받을 배열과 동일한 크기의 LIS 배열을 생성합니다.
   int[] nums: 수열의 값을 입력 받을 배열
   int[] lis: 최장 증가 부분 수열을 나타낼 배열, default는 0
   int[] idx: i번 째 인자는 몇 번째 LIS 인자임을 나타내는 배열
   len: LIS의 길이(배열의 길이와는 무관)
2. 배열의 값을 입력 받고, 첫 번째 인자를 LIS의 첫 번째 인자로 할당 및 lisLen = 1로 설정한 후 본격적인 LIS에 대한 탐색이 시작됩니다.
3. 수열의 두 번째 인자부터 for 반복문을 통해 target 으로 설정 후 LIS의 마지막 인자와 비교합니다.
4. 만약 LIS의 마지막 인자보다 큰 경우에는 lis[lisLen]에 target을 넣은 후 lisLen을 1 더해주며, i번째 idx 배열 값으로 len을 넣습니다(수열의 i번째 인자가 몇 번째 LIS 인자임을 입력).
5. LIS의 마지막 인자보다 작은 경우에는 LIS중 target보다 큰 첫 번째 수를 target으로 변경합니다.
   교체를 하는 것으로 LIS가 완성되는 것은 아니지만, LIS의 길이 자체는 변하지 않습니다.
   
   예를 들어 아래와 같은 수열 A가 있는 경우, 정확한 LIS와 교체를 통해 만들어진 LIS가 동일하지는 않지만 길이 자체는 동일합니다.
   
   A = {10, 20, 30, 15, 40} 
   Right LIS = {10, 20, 30, 40}, length =4
   Replace LIS = {10, 15, 30, 40}, length = 4
6. 5번 동작에서  4번과 동일하게 i 번째 idx 배열 값으로 교체된 인덱스의 값을 넣어 수열의 i 번째 인자가 몇 번째 LIS 인자인지 나타냅니다.
7. LIS의 길이를 나타내는 len 객체를 이용해 idx 배열의 n-1 번째 인자부터 0번째 배열까지 탐색하며 len과 동일한 idx 값이 나타나면 해당 인덱스의 nums 값을 stack에 넣고 len을 1씩 감소합니다.
8. 모든 범위 탐색이 완료된 후 stack을 pop으로 추출하여 LIS의 부분 수열을 출력합니다.

 

 

 

 

---

 

 

 

 

 

| 풀이

 

 

 

import java.io.*;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] nums = new int[n];
		int[] lis = new int[n];
		int[] idx = new int[n];
		
		for(int i = 0; i<n; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		//LIS의 첫 번째 인자는 수열의 첫 번째 인자로 할당 및 lis 길이는 1로 초기화
		lis[0] = nums[0];
		int len = 1;
		
		//수열의 두 번째 인자부터 탐색
		for(int i = 1; i<n; i++) {
			int target = nums[i];
			
			//LIS의 마지막 인자보다 i번째 인자가 크다면 LIS에 추가 및 LIS 길이 증가
			if(target>lis[len-1]) {
				lis[len] = target;
				idx[i]=len;
				len++;
			}
			//LIS의 마지막 인자보다 작다면, targer보다 첫 번째로 큰 값을 targer으로 바꾸기 위해 이분탐색을 진행.
			else {
				int s = 0;
				int e = len-1;
				
				while(s<e) {
					int mid = (s+e)/2;
					//int mid = (s+e)>>>1;
					
					if(target>lis[mid]) {
						s = mid + 1;
					}
					else
						e = mid;
				}
				lis[s] = target;
				//i번째 인자는 s번째 LIS 인자
				idx[i] = s;
			}
		}
		sb.append(len).append('\n');
		
		//LIS의 len번째 인자부터 0번째 인자까지 stack에 넣음
		Stack<Integer> stack = new Stack<>();
		for(int i = n-1; i>=0; i--) {
			if(len == idx[i]+1) {
				stack.add(nums[i]);
				len--;
			}
		}
		
		//LIS의 0번째 인자부터 len번째 인자까지 출력하여 부분 수열을 나타냄
		while(!stack.isEmpty()) {
			sb.append(stack.pop()).append(" ");
		}
		
		bw.write(sb.toString());
		br.close();
		bw.close();
	}
}