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

 

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

수열의 크기가 1,000,000으로 

가장 쉬운 방법인 O(n^2)의 방식으로 증가수열의 길이를 구하기에는 시간초과가 나는 문제입니다.

 

따라서 최소 O(NlogN)로 동작하는 알고리즘을 설계해야 합니다.

이분탐색을 이용하여 증가수열의 길이를 구하는 방식이 존재합니다.

단, 이 방식으로는 수열의 길이만 알 수 있고 수열은 알 수 없습니다. 물론, 수열을 알고 싶다면 추가로 수정을 하면 됩니다.

 

우선 문제의 예시로 증가수열을 설명하겠습니다.

10	20	10	30	20	50
1	2	1	3	2	4

[10 20 10 30 20 50] --> [10,20,30,50] (길이 4)

 

* [10, 20, 10, 30, 20, 50]

처음 arr에는 10이 들어가 있는 상태로,

그 이후부터 들어갈 원소와 arr에 들어있는 '마지막 원소'와 비교를 시작합니다.

1) '마지막 원소'보다 큰 경우에는 arr에 삽입

2) '마지막 원소'보다 작은 경우에는 arr 배열 내에서 들어갈 원소보다 크거나 같은 값 중 가장 작은 값과 변경

--> 이 방식이 '길이'에는 아무런 영향을 주지 않습니다.

 

맨 처음 arr[0] = 10,

 

1) 20이 들어온 경우 arr[0] < 20이므로 arr에 삽입, arr의 마지막 원소는 arr[1]인 20이 되었음.

2) 10이 들어온 경우 arr[1] > 10이므로 arr에 삽입하지 않고, 10보다 크거나 같은 수 중 가장 작은 수가 있는

     arr[0]의 값을 10으로 변경해줌.   (arr의 사이즈는 여전히 2)

3) 30이 들어온 경우 arr[1] < 30이므로 arr에 삽입, arr의 마지막 원소는 arr[2]인 30이 되었음.

4) 20이 들어온 경우 arr[2] > 20이므로 arr에 삽입하지 않고, 20보다 크거나 같은 수 중 가장 작은 수가 있는

     arr[1]의 값을 20으로 변경해줌.  (arr의 사이즈는 여전히 3)

5) 50이 들어온 경우 arr[2] < 50이므로 arr에 삽입, arr의 마지막 원소는 arr[3]인 50이 되었음.

 

이 때의 arr의 size가 증가수열의 길이가 됩니다.

 

 

[7 1 5 2 3]의 입력으로 예시를 하나 더 들어보겠습니다.

 

맨 처음 arr[0] = 7,

1) 1이 들어온 경우 arr[0] > 1이므로 arr에 삽입하지 않고, 1보다 크거나 같은 수 중 가장 작은 수가 있는

      arr[0]의 값을 1로 변경해줌. 

2) 5가 들어온 경우 arr[0] < 5이므로 arr에 삽입. arr의 마지막 원소는 arr[1]인 5가 되었음.

3) 2가 들어온 경우 arr[1] > 2이므로 arr에 삽입하지 않고, 2보다 크거나 같은 수 중 가장 작은 수가 있는

       arr[1]의 값을 2로 변경해줌.

4) 3이 들어온 경우 arr[1] < 3이므로 arr에 삽입, arr의 마지막 원소는 arr[2]인 3이 되었음.

 

이 때의 arr의 size가 증가수열의 길이가 됩니다.

 

위의 방식은 증가수열의 형태는 다를 수 있어도 길이는 항상 최대를 보장합니다.

(1, 2, 4)와 (3,5,7)의 길이는 같습니다.

증가수열을 만드는 입장에서 항상 유리한 상태는 '마지막 원소'가 최대한 작은 상태가 유리합니다.

삽입될 원소가 마지막 원소보다 크기만 하다면 유리한데,

[ 3 5 4 7 ] '길이'의 입장에서 [3,5,7]과 [4,5,7]은 동일합니다.

여기서 3을 4로 바꿔준 의미는 단순히, '4'에서도 최장 증가수열의 길이의 가능성이 있기 때문에

바꿔준 것일 뿐이고 이 상태는 '3'에서 시작한 증가수열의 길이를 아직 가지고 있습니다.

[ 3 5 4 7 1 2 3 4 ] 

이런 식으로 들어왔을 경우

[4 5 7] -> [1 2 3 4] 로 변경의 가능성이 있기 때문에 들어온 수보다 큰 값중 가장 작은 값을 게속 갱신하여

변경해주는 것입니다.

[4 5 7] -> [1 2 3 4] 로 변경이 되면서 세번 째 4의 증가수열 가능성은 이미 벗어나버렸음을 갱신.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> arr;

int main(void)
{
	int n;
	cin >> n;
	int temp;
	cin >> temp;
	arr.push_back(temp);
	int idx = 1;

	for (int i = 2; i <= n; i++)
	{
		cin >> temp;
		if (temp > arr[idx - 1])
		{
			arr.push_back(temp);
			idx++;
		}
		else
		{
			int id = lower_bound(arr.begin(), arr.end(), temp) - arr.begin();
			arr[id] = temp;
		}
	}

	cout << idx;
}