[백준][플래티넘 5][LIS] 14003. 가장 긴 증가하는 부분 수열 5

💡 	이분 탐색 O(logN)
	가장 긴 증가하는 부분 수열(LIS) O(n log n)

[문제]

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

[입력]

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

 

[출력]

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

 

 

[풀이]

비슷한 유형의 문제이지만 조건만 다른 문제인 가장 긴 증가하는 부분 수열 4는 DP를 사용해서 풀 수 있지만 이 문제는 N의 범위가 크기에 DP를 사용하면 시간초과를 받게 된다. LIS 알고리즘, 저장 위치에 배열 저장 방법으로 접근했다.

    1. 오름차순을 유지하는 lenList 배열

    2. 이분 탐색 내장 함수를 사용해 오름차순을 유지하면서 현재 값(v)이 들어갈 수 있는 자리(insertPos)를 찾는다.

    3. 최장 증가 수열 길이를 알기 위해 인덱스 저장 배열(idxList)에 insertPos를 할당한다.

    4. 최장 증가 수열 출력을 위해 뒤부터 탐색하며 감소하는 size에 맞는 idxList[i를 출력한다.

필요한 데이터 발견)
idxList[i] = Integer.MAX_VALUE; 부분을 추석처리 해도 AC를 받는 문제
입력 범위만 다른 문제인 가장 긴 증가하는 부분 수열 2 에는 제출하면 틀렸습니다를 받지만
해당 문제에는 아래의 테스트케이스가 없는 모양이다.

Input:
4
1 3 3 2

Answer:
2
1 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int size = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] inputList = new int[N];
		int[] idxList = new int[N];
		int[] lenList = new int[N];
		
		for (int i = 0; i < N; i++) {
			int v = Integer.parseInt(st.nextToken());
			inputList[i] = v;
			
			int pos = Arrays.binarySearch(lenList, 0, size, v);
			if(pos >= 0) {
				idxList[i] = Integer.MAX_VALUE; // 주석처리 해도 통과가 되는 문제점 발견
				continue;
			}
			
			int insertPos = Math.abs(pos) - 1;
			lenList[insertPos] = v;
			idxList[i] = insertPos;
			
			if(insertPos == size) size++;
		}

		int len = size;
		StringBuilder sb = new StringBuilder();
		sb.append(size + "\n");
		
		for (int i = N-1; i >= 0; i--) {
			if(idxList[i] == size-1) {
				lenList[--size] = inputList[i];
				if(size == 0) break;
			}
		}
		
		for (int i = 0; i < len; i++) sb.append(lenList[i] + " ");
		System.out.print(sb);
	}
}

 

 

[결과]

---

백준(BOJ) 문제 중 [ 14003. 가장 긴 증가하는 부분 수열 5 ] 문제를 풀고 정리한 내용입니다.