12015 가장 긴 증가하는 부분 수열 2

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


public 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 number [] = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		
		for(int i=0; i<N; i++) {
			number[i]= Integer.parseInt(st.nextToken());
		}
		
		
		ArrayList<Integer> list = new ArrayList<>();
		list.add(0);
		
		for(int i = 0 ; i<N; i++) {
			int value = number[i];
			
			if(list.get(list.size() -1 )< value) {
				list.add(value);
				
			}else {
				int left = 1;
				int right = list.size()-1;
				
				while(left< right) {
					int mid = (left+right)/2;
					if(list.get(mid)<value) {
						left = mid+1;
					}else {
						right = mid;
					}
				}
				
				list.set(right, value);
			}
		}
	
		
		System.out.println(list.size()-1);
	}
}

 

 

다른 블로그를 많이 참고했다.

예를 들어 설명하겠다.

5 10 1 2 3

 

이렇게 값이 있다고 해보자.

그러면 5 10 이 일단 증가하는 부분 수열이다.

 

그렇다면 5 10 1 은 증가하는 부분 수열이 아니다.

이때, 이 문제의 아이디어는

5대신 1을 대체한다.

즉, 1 10을 만든다.

 

왜냐하면, 증가하는 부분 수열을 출력하는 게 아니라, 증가하는 부분 수열의 길이를 출력하라고 했기 때문이다.

5 10 은 그 길이가 2이다.

1 10 역시 그 길이가 2이다.

결국 길이가 같기 때문에, 5대신 1로 대체해도 결과는 같다.

 

그럼 왜 대체하느냐!

만약에 5 10 다음에 1이 나왔을 때,

5를 1로 대체하지 않고

그냥 5 10 이 상태로 둔다고 하자.

 

그러면 그 다음에 2가 나온다.

5 10 2 가 증가하는 부분 수열이 아니기 때문에,

이 경우도 그냥 5 10 이 된다.

 

그 다음에 3이 나온다.

그럼 이 경우도 그냥 5 10으로 둘 것이다.

결국 최종적으로 5 10, 즉 길이가 2가 된다.

 

하지만, 5 10 1 2 3 에서

(앞 부분의) 5 10은 증가하는 부분 수열의 길이가 2이지만,

(뒷 부분의) 1 2 3 은 그 길이가 3이다.

 

따라서 5대신 1로 대체했다면,

5 10

1 10

1 2

1 2 3 

이렇게 채워져서, 그 길이가 최종적으로 3으로 리턴될 수 있다.

 

즉, 5대신 1로 대체한 이유는, 1다음에 5보다 작은 수들이 나왔을 경우,

증가하는 수열을 더 길게 만들 수 있기 때문이다.

 

그래서 이 문제는

기존에 수열을 만들어놓고, 다음에 나오는 숫자에 따라 수열을 변화시킨다.

 

1) 다음에 오는 숫자가 더 클 경우

예를 들어 5 10 12 라 하자.

 

그러면 그냥 수열에 5를 두고, 10을 두고, 12 를 두면 된다.

즉 수열이 5 10 12 가 된다.

 

2) 다음에 오는 숫자가 작은 경우

 

예를 들어 5 10 1 2 3 인 경우,

 

위에서 설명한 것처럼

5 10

1 10

1 2

1 2 3 

 

이렇게 변화시킨다.

 

위와 같이 변화된 이유는 이분분할 코드 때문이다.

코드에서 보이듯이, 리스트를 활용해서 문제를 푼다.

5 10 1 2 3 이 나왔을 때, 

증가하는 부분 수열을 만들려고 이 값들을 list 에 넣는데,

우선 리스트에 0부터 넣는다.

이는 맨 처음에 입력으로 주어진, ( 5 10 1 2 3 의 경우 5) 값과 비교를 쉽게 하기 위해서이다.

그래서 리스트에 0을 먼저 넣고,

그 후 5를 리스트에 넣는다. 그리고 10도 증가하는 수열이기 때문에 리스트에 넣는다.

리스트에 0 5 10 이 들어가 있을때,

left 는 5의 인덱스, right 는 10 의 인덱스를 의미하며,

left = 1, right = 2 이다.

그렇다면 mid = (left + right) / 2= 1이다. (int 형으로 받기 때문)

 

그런데 list.get(mid) = 5 이고, value = 1로,

(value 는 다음에 오는 값을 의미함. 즉 5 10 다음에 1이 나옴)

 

list.get(mid) > value 이기 때문에

right = mid = 1 이 되고,

left = right = 1 이므로

이때 while 문을 탈출하면서,

list.set(right, value) = list.set(1,1) 

즉, 리스트 인덱스 1의 위치에 값 1을 넣는 것이다.

(list.set(1,1) 에서, 앞의 1이 인덱스를 의미, 뒤의 1이 값을 의미)

 

이런 식으로 진행되면서 대체가 된다.

 

 

참고 블로그 :

https://gre-eny.tistory.com/23

[java] 백준 12015 (가장 긴 증가하는 부분 수열 2) Gold 2