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

백준 P5 14003 가장 긴 증가하는 부분수열5

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

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

백준에 가장 긴 증가하는 수열 시리즈가 있는데 그 중 플래티넘5로 끝판왕격인 놈이다.

LIS로 풀면 되겠거니 했는데 LIS에서 같은 위치를 참조하는 수일때 뒤에 입력되는 원소를 출력하는 로직을 처리하는게 까다로웠다.

 

문제 풀이

1. binarySearch로 LIS에 가장 긴 증가하는 수열의 원소를 넣어준다.

2. 입력 배열의 원소가 LIS 배열에서 어떤 위치에 있는지 기록하는 index 배열을 만들어준다.

arr = {10, 20, 10, 30, 20, 50}

LIS = {10, 20, 30, 50}

index = {0, 1, 0, 2, 1, 3}

size = 4(부분수열의 길이)

3. index를 N부터 0까지 탐색하면서 index[i]가 3, 2, 1, 0인 arr 원소를 결과 리스트에 저장한다. 

4. 결과 리스트를 역순으로 출력한다.

 

package boj;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class BOJ_P5_14003_가장긴증가하는부분수열5 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		
		for(int i=0; i<N; i++)	arr[i] = sc.nextInt();
		
		int[] LIS = new int[N];
		int[] index = new int[N];
		int size = 0;
		LIS[size] = arr[0];
		index[0] = size++;
		
		for(int i=1; i<N; i++) {
        	// LIS에서 0부터 size까지 arr[i]가 있는 위치를 찾는다.
			int pos = Arrays.binarySearch(LIS, 0, size, arr[i]);
            // 만약 binarySearch 결과가 음수면 LIS에 존재하지 않는다는 뜻
            // -(원래 있어야 할 위치) -1이 반환됨
            // LIS = {10}, 찾는 값이 20이면 -1-1 = -2가 반환 
			if(pos < 0)
				pos = Math.abs(pos) - 1;
			LIS[pos] = arr[i];
			index[i] = pos;
            // pos이 size와 같으면 LIS의 맨 뒤에 원소가 추가됐으니 size를 1 늘려준다.
			if(pos == size) 
				size++;
		}
		
		System.out.println(size);
		
		ArrayList<Integer> answer = new ArrayList<Integer>();
		for(int i=N-1; i>-1; i--) {
			if(index[i] == size-1) {
				size--;
				answer.add(arr[i]);
			}
            
            // size == -1이란 말은 부분수열을 전부 찾았다는 뜻이므로 탐색 종료. N이 백만이라서 시간복잡도를 줄여주기 위해 넣음
			if(size == -1)
				break;
		}
		int len = answer.size()-1;
		for(int i=len; i>=0; i--)
			System.out.printf("%d ",answer.get(i));
	}
}

 

정리

LIS 배열을 찾는 코드는 O(NlogN)이고 나머지는 모두 O(N)이니 전체 시간 복잡도는 O(NlogN)이 나온다. 부분 수열의 출력 조건이 같은 LIS 위치일 때 먼저 입력되는 값이라고 생각해서 며칠을 헤맸었다. 문제를 꼼꼼하게 보자..ㅠㅠㅠ