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

 

| 문제 링크

 

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

12738번: 가장 긴 증가하는 부분 수열 3

 

 

 

 

---

 

 

 

 

| 문제

 

 

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

 

 

 

 

---

 

 

 

 

| 풀이

 

 

해당 문제는 수열의 크기가 1,000,000으로 DP로 풀 경우 시간초과가 발생하며, 이분 탐색(lower bound)을 통해 LIS의 개수를 구했습니다(가장 긴 증가하는 부분 수열 2와 같은 문제입니다).

 

 

1. 수열의 값을 입력 받을 배열과 동일한 크기의 LIS 배열을 생성합니다.
   int[] nums: 수열의 값을 입력 받을 배열
   int[] lis: 최장 증가 부분 수열을 나타낼 배열, default는 0
   lisLen: LIS의 길이(배열의 길이와는 무관)
2. 배열의 값을 입력 받고, 첫 번째 인자를 LIS의 첫 번째 인자로 할당 및 lisLen = 1로 설정한 후 본격적인 LIS에 대한 탐색이 시작됩니다.
3. 수열의 두 번째 인자부터 for 반복문을 통해 target 으로 설정 후 LIS의 마지막 인자와 비교합니다.
4. 만약 LIS의 마지막 인자보다 큰 경우에는 lis[lisLen]에 target을 넣은 후 lisLen을 1 더해 줍니다.
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

 

 

 

 

---

 

 

 

 

| 코드

 

 

import java.io.*;
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));
		
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] nums = new int[n];
		int[] lis = new int[n];
		
		//순열에 값 입력
		for(int i = 0; i<n; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		//lis의 첫 번째 인자는 순열의 첫 번째 값으로 할당
		lis[0]=nums[0];
		int len = 1;
		
		//순열의 2번째 인자부터 lis에 해당하는지 이분 탐색(lower bound)
		for(int i = 1; i<n; i++) {
			int target = nums[i];
			
			if(target>lis[len-1]) {
				lis[len]=target;
				len++;
			}
			else {
				int s = 0;
				int e = len-1;
				
				while(s<e) {
					int mid = (s+e)/2;
					//lis의 중앙 값이 target보다 같거나  크다면 start부터 mid까지 재탐색
					if(target<=lis[mid])
						e = mid;
					//lis의 중앙 값이 target보다 작다면 mid+1부터 end까지 재탐색
					else
						s = mid + 1;
				}
				lis[s] = target;
			}
		}
		
		bw.write(String.valueOf(len));
		br.close();
		bw.close();
	}

}