백준14003 가장 긴 증가하는 부분 수열5 - C++

가장 긴 증가하는 부분 수열 시리즈 중

난이도가 높은 5이다.

 

일반적인 방법으로 풀 수 없는 제한 조건이 있다.

수열의 크기가 100만이고, 숫자가 -10억부터 10억까지이므로

기존에 2에서 쓰던 방법들은 시간이 너무 오래 걸린다.

 

배열을 한 번 순회하면서 O(N)

논리적으로 저장하는 방식이 O(logN)이라면

NlogN ~ 2천만 회 정도로 1초 안에 풀이가 가능하다.

 

사용할 방법은 백트레킹이다.

 

이름이 어려워 보이지만,

단순히 내가 한 행동을 저장해 놓고

나중에 다시 꺼내보겠다는 얘기이다.

 

방식은 다음과 같다.

 

1. 주어진 수열(A)을 순회한다.

2. 가장 긴 부분 수열을 저장하는 수열(B)에 저장한다.

3. 가장 긴 수열이 저장되었다면, 저장한 값이 A에서는 몇 번째인지 

백트레킹으로 추적한 후 저장한다.

 

---

예시

1. 가장 먼저 저장할 수열 B를 세팅한다.
   B[0] = -1,000,000,001을 저장한다.(수열 내에서 절대 나올 수 없는 작은 수)
   굳이 이렇게 하는 이유는
   처음 B[0]에 저장할 때 if 문으로 예외 처리하고 싶지 않아서(코드를 간결히 하고 싶어서)
   나올 가능성 없는 작은 수를 넣어서 코드 작성에 일관성을 주고 싶어서이다.
2. 주어진 수열 A를 순회해 보자.
   A 는 [10, 20, 10, 30, 20, 50]이다.
   i = 0 일 때, A[i] = 10이다.
   A[i] 가 현재 B에 마지막으로 저장된 숫자보다 크면
   B는 증가하는 수열이 유지되므로 B의 마지막 다음에 넣어준다.
3. B[++idx] = A[i] 를 넣어주자. (현재 idx=0이고, B[1] 에 저장된다.)
4. 만약 B의 마지막 숫자보다 같거나 작다면
   B에 넣을 경우 증가하는 수열이 되지 못하기 때문에 넣지 않는다.
   대신, B에 들어갈 수 있는 가장 빠른 자리를 찾아서 해당 자리에 넣어준다.
   이는 가장 긴 수열만 유지하면 되기 때문에,
   중간 숫자가 바뀌는 것은 가장 긴 수열에 영향을 주지 않기 때문이다.
   다만, 어떤 부분 수열인지 알아야 하기 때문에 모든 과정을 tracking에 차례대로 저장한다.

문제에서 준 예시를 보자.

 

A = [10, 20, 10, 30, 20, 50]

B = [-INF]  (INF = -1,000,000,001)

i	설명	B 배열 상태
0	A[0] = 10 이고, B[0] = -INF 보다 크기 때문에 B[1] = 10 을 넣어준다. tracking 에 (1, A[0]) 을 넣어준다. (이는 B의 1번째 자리에 10이 들어갔다는 뜻이다.)	B = [-INF, 10 ]
1	A[1] = 20 이고, B[1] = 10 보다 크기 때문에, B[2] = 20 을 넣어준다. tracking 에 (2, A[1]) 을 넣는다.	B = [-INF, 10, 20]
2	A[2] = 10 이고, B[2] = 20 보다 작기 때문에, B에 들어갈 수 있는 가장 앞쪽의 같거나 작은 수인 B[1] = 10 에 넣는다. tracking 에 (1, A[2])을 추가한다. (이는 B의 1번자리에 A[1]이 들어갔다는 뜻이다.)	B = [-INF, 10, 20]
3	A[3] = 30 이고, B[2] = 20 보다 크기 때문에, B[3] = 30 을 넣어준다. tracking 에 (3, A[3]) 을 추가한다.	B = [-INF, 10, 20, 30]
4	A[4] = 20 이고, B[3] = 30 보다 작기 때문에, B에 들어갈 수 있는 가장 앞쪽의 같거나 작은 수인 B[2] = 20 에 넣는다. tracking 에 (2, A[4])을 추가한다.	B = [-INF, 10, 20, 30]
5	A[5] = 50 이고, B[3] = 30 보다 크기 때문에, B[4] = 50 을 넣어준다 tracking 에 (4, A[5]) 을 추가한다..	B = [-INF, 10, 20, 30, 50]

 

A의 순회가 종료되었다.

 

가장 긴 부분 수열인 B의 길이는 5이지만 -INF는 내가 강제로 넣어준 값이므로 빼줘서

가장 긴 부분 수열의 길이는 4가 나온다.

 

이때, 길이를 구하는 것이 아니라 가장 긴 부분 수열을 출력해줘야 하므로 백트래킹을 한다.

 

지금 B는 같은 숫자들이 나와서 정답과 똑같이 보이지만 실상은 다르다.

 

B에 저장된 값들의 index가 앞뒤 순서가 바뀌어있을 수도 있기 때문인데,

실제로 위의 과정을 거치면 B에 저장된 A의 인덱스는 다음과 같다.

 

B = [-INF, 10, 20, 30, 50] => index of A = [-INF, 2, 4, 3,5 ] 

 

실제로 A[2], A[4], A[3], A[5] 는 [10, 20, 30, 50] 이므로 증가하는 수열처럼 보이겠지만

A의 index가 차례대로 증가해야 부분수열이므로 해당 수열은 엉터리이다.

 

그러므로 내가 언제 어떻게 B를 바꿨는지 거꾸로 tracking 해가며 

맞는 인덱스의 숫자로 바꾸어 준다.

 

잘 생각해 보자.

 

B의 가장 마지막인 4번째 B[4] 에 저장된 숫자는

B[3] 보다 나중에 저장되었어야 한다.

왜냐하면, B[3] 이 저장되기 전까지는 B[4]가 저장될 수 없기 때문이다.

그러므로, B[4] 를 저장하기 전에 저장된 B[3] 만이 유효하며,

B[4]를 저장한 후 B[3]가 바뀌었다면 유효하지 않다.

그러므로 B[4] 를 저장한 시점이 나올 때까지 앞쪽의 변화들은 싸그리 무시한다.

 

그렇다면 같은 인덱스에 있는 숫자가 여러 번 바뀌었다면 어떻게 될까?

B[4]를 i = 5에서도 했고, i = 6에서도 했다면 어떤가?

사실 둘 다 정답으로 처리된다.

둘 다 증가하는 수열을 만족하기 때문에, 

가장 먼저 저장이 되었건 나중에 저장이 되었건,

내 앞의 숫자보다만 나중에 저장되면 항상 증가하는 수열이 보장된다!

 

마찬가지로 B[3]는 B[2] 이후에 저장이 되어야 하므로

마지막으로 B[3]가 저장된 시점이며 동시에 B[4]가 저장되기 이전의 시점에서 가장 최근 것을 찾는다.

 

예시로 보자.

 

A 수열의 길이는 6이므로 tracking에 저장된 기록도 6개이다.

tracking index를 j로 두고 추적해 보자.

B에 저장된 개수는 5개이므로 B의 인덱스를 idx=4로 두고 생각한다.

j	idx	설명	유효식
5	4	tracking[j] = (4, 50) 이고, idx=4 이므로 4 위치에서 가장 최근에 업데이트 된 숫자를 찾았으므로 50을 저장한다. idx=3 변경하여 B[3]이 저장된 시점을 찾는다.	B[4] = 50; idx--;
4	3	tracking[j] = (2, 20) 이고, idx=3이므로  B[3]을 저장한 이후에 B[2]가 바뀌었으므로 무효다. 패스
3	3	tracking[j] = (3, 30) 이고, idx=3이므로 가장 최근에 업데이트된 B[3]이다.  30으로 바꾸어주고 idx를 줄인다.	B[3] = 30; idx--;
2	2	tracking[j] = (1, 10) 이고, idx=2이므로 무효다. 패스
1	2	tracking[j] = (2, 20) 이고, idx=2이므로  가장 최근 업데이트다.  20으로 바꾸어주고 idx를 줄인다.	B[2] = 20; idx--;
0	1	tracking[j] = (1, 10) 이고, idx=1이므로 가장 최근 업데이트다. 10으로 바꾸어주고  idx를 줄인다.	B[1] = 10; idx--;

이렇게 tracking을 돌면 index가 오름차순인 B배열이 완성되고

증가수열이 항상 보장된다.

 

원래 걸릴 시간 복잡도는 A 순회 O(N) * B에 넣을 자리 찾기 O(N) + 백트래킹 O(N) 이므로 O(N^2 + N)이지만,  

B에 넣을 자리 찾기는 B가 항상 오름차순으로 저장되어 있기 때문에

이분 탐색 O(logN)을 사용하여 총복잡도를 O(NlogN + N)으로 낮출 수 있다.

N = 100만까지이므로

C++에서 최악의 경우에도 0.3초 이내로 풀 수 있을 것으로 기대할 수 있다.

#include <cstdio>
#include <vector>
using namespace std;

int arr[1000001];
int dp[1000001];

vector <pair<int, int> > tracking;// dp 에 저장된 idx, value 저장

int N;
int lowerBound(int idx, int arrValue);
int solve();
void printTrace();

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", arr + i);
	}
	printTrace();
	return 0;
}


int solve() {
	int idx = 0;//dp 에 저장할 인덱스
	dp[0] = -1000000001; // 숫자 범위 -10억 ~10억
	//한 번 순회
	for (int i = 1; i <= N; i++) {
		 //dp의 현재 idx에 있는 숫자보다 클 경우 추가
		if (dp[idx] < arr[i]) {
			dp[++idx] = arr[i];
		//경로저장
			tracking.push_back(make_pair(idx, arr[i]));
		}
		//아닐경우 arr[i]의 숫자보다 (같거나 작은 수 중 가장 앞에 있는 수)를 dp에서 찾아 교체 
		else {
			int idxChange = lowerBound(idx, arr[i]);
			dp[idxChange] = arr[i];
		//경로저장
			tracking.push_back(make_pair(idxChange, arr[i]));
		}
	}
	return idx;
}

int lowerBound(int idx, int arrValue) {
	int s=0, m, e=idx;
	int ret = e;
	while (s <= e) {
		m = (s + e) / 2;
		//dp 값보다 같거나 작은 자리에 저장해야 증가하는 수열 가능
		if (dp[m] >= arrValue) {
			e = m-1;
			ret = m;
		}
		else {
			s = m + 1;
		}
	}
	return ret;
}

void printTrace() {
	int Num = solve();
	int idx = Num;
	printf("%d\n", Num);

	
	//tracking 된 정보 순회 -> dp배열 정정
	for (int i = tracking.size()-1; i >= 0; i--) {
		//갱신된 순서 맞는지 확인 -> 5자리에 저장된 것은 4자리에 저장된 것보다 늦게 저장되어야함
		if (tracking[i].first == idx) {
			dp[idx--] = tracking[i].second;
		}
	}
	for (int i = 1; i <= Num; i++) {
		printf("%d ", dp[i]);
	}

}