[백준 BOJ 13711 glod1 - LCS4] Longest Common String (LCS) C++

백준 13711 LCS4

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

13711번: LCS 4

 

https://steptoprogrammer.tistory.com/60

[백준 BOJ 17218 glod5 - 비밀번호 만들기] Longest Common String (LCS) C++

앞서 올렸던 비밀번호 만들기 풀이와 비슷하게 2차원 배열 dp로 LCS의 길이를 구하려고 했었다.

하지만 여기서 N은 10000 이고, 2차원 배열로 하면 100000x100000으로 메모리 초과가 나게 된다.

 

그래서 생각한 방법이..

sliding window기법으로 dp[2][100000]으로 시도했지만, 시간 초과가 났다. 

 

메모리가 문제가 아니라 이 문제에서는 시간을 줄이는게 문제였다

 

 

 

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

이 조건을 잘보면, 1부터 N까지의 숫자가 모두 한번씩 등장한다고 한다.

 

수열이

A : 1 2 3
B : 1 3 2

이렇게 주어졌을 때,

 

두번째 수열을 첫번째 수열의 기준으로 정렬한다면 

1 -> 수열 A의 0번째 : 0

3 -> 수열 A의 2번째 : 2

2 -> 수열 A의 1번째 : 1

 

B는 1 3 2 -> {0 2 1}

으로 두고 이 수열에서 LIS, 즉 증가하는 가장 긴 부분 수열의 길이를 구한다면 그것이 두 수열의 LCS가 된다. 

이게 가능한 이유는 두 수열 모두 다 중복 된 수 없이 같은 수들이 나오기 때문이다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <string>
#include <string.h>
#include <iostream>

using namespace std;

int N;
int s1[100001];
//int s2[100001];
int idx[100001];
vector <int> v;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; i++) {
		//cin >> s1[i];
		int x;
		cin >> x;
		s1[x] = i;
	}
	for (int i = 0; i < N; i++) {
		//cin >> s2[i];
		//idx[i] = lower_bound(s1, s1 + N, s2[i]) - s1;
		int x;
		cin >> x;
		idx[i] = s1[x];
		//cout << idx[i] << " ";
	}
	v.push_back(idx[0]);
	for (int i = 1; i < N; i++) {
		if (v.back() < idx[i]) {
			v.push_back(idx[i]);
		}
		else {
			int in = lower_bound(v.begin(), v.end(), idx[i]) - v.begin();
			v[in] = idx[i];
		}
	}
	cout << v.size();
}

주석 친 코드들은 처음에 제출해서 틀렸던 코드이다.

B 수열을 A기준으로 바꾼 배열을 구하려고 할때, A안에서 lower_bound로 인덱스를 찾으려고 했다.

왜 틀렸는지 한참을 고민했다... 

lower_bound는 정렬된 배열 혹은 벡터에서 사용하는 함수임을 간과한 것이다.

(그래서 lower_bound 관련 내용을 다시 정리했다.... 바보)

lower bound 정리 글

https://steptoprogrammer.tistory.com/61?category=977806 

C++ upper_bound , lower_bound 이용하기 / 알고리즘

 

A기준으로 B를 정렬한 배열(idx)을 구하고 나서 , idx의 LIS길이를 구해주면 된다. 

여기서 LIS를 구할 때 , 이중 for문 으로 구하는 것 보다는 위의 방법을 사용하면 시간 복잡도를

N*N -> NlogN

으로 줄일 수 있다. 

 

 

O(NlogN)으로 배열의 LIS구하기

1. 첫번째 원소를 벡터에 넣는다.

2. 두번째 원소부터 돌면서 벡터의 가장 뒤의 값(v.back() , 혹은 v[v.size()-1]) 과 비교한다.

     - v.back보다 크다면 벡터에 push_back 한다.

     - v.back보다 작다면, lower_bound로 이 값보다 크거나 같은 수가 위치한 인덱스를 찾아 그 위치에 값을 넣는다.

3. 마지막에 이 벡터의 크기가 lis의 길이가 된다.(이 벡터의 원소들이 lis는 아님을 유의)