알고리즘/탐욕법

백준 30805 - 사전 순 최대 공통 부분 수열

hvv_an 2025. 6. 15. 14:21

문제 설명

어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.

  • 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.
  • 예를 들어, 는 의 부분 수열이지만, 의 부분 수열은 아닙니다.

또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.

  • 두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.
  • 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.
  • 길이가 인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.

양의 정수로 이루어진 길이가 N인 수열 이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 인 수열 이 주어집니다.

수열 와 수열 가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하세요.

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

 

 

 

 

 

 

제한 사항

 

 

 

 

 

 

풀이

문제를 요약하면 두 수열 A, B가 주어지면 사전순으로 가장 늦는 공통 부분 수열을 구하면 된다.

사전순으로 늦는 기준은 숫자가 크거나 모든 숫자가 동일하다면 길이가 더 긴 부분 수열이 더 늦는 것이다.

 

해당 문제를 처음 봤을 때는 KMP처럼 공통 부분  수열을 찾은 뒤 역으로 추적하고 가장 큰 숫자가 나올 때까지 제거하면 될 것이라 생각했다.

하지만 이렇게 풀었더니 시간 초과가 발생했다.

 

이 문제는 다른 접근 방식으로 풀어야 한다.

바로 정렬이다.

사전순으로 가장 늦는 부분 부분 수열은 앞이 가장 큰 부분 수열인 것은 명확하다.

즉, 길이가 어찌 되든 가장 큰 숫자를 찾아내면 된다.

그리고 길이가 더 긴 부분 수열이 유리하므로 가장 큰 숫자가 여러 개라면 되도록 앞에 나오는 숫자를 선택하는 것이 유리하다.

 

그럼 숫자가 큰 순서로 정렬하되 앞에 등장한 숫자부터 정렬되도록 기준을 세우면 된다.

bool cmp(pair<int,int> a, pair<int,int> b) 
{
	if (a.first == b.first) return a.second < b.second;
	return a.first > b.first;
}

이렇게 정렬된 숫자를 앞에서부터 따라가며 A와 B가 동일한 숫자라면 정답에 추가하면 된다.

단 앞에서 등장한 큰 숫자보다 뒤에 등장하는 숫자만 추가해야 한다.

예를 들어, {3, 2}, {2, 1}, {1, 3}이라 했을 때 두 번째 숫자 2를 추가하려 해도 3보다 앞에 등장한 숫자이기 때문에 2는 유효하지 않은 숫자이다.

이를 관리하기 위한 변수와 실제 인덱스를 가리키는 변수를 분리하여 관리하면 된다.

int idxA = 0, idxB = 0;
int rightA = 0, rightB = 0;

vector<int> ans;
while (idxA < N && idxB < M)
{
	if (A[idxA].first == B[idxB].first)
	{
		if (rightA > A[idxA].second) idxA++;
		else if (rightB > B[idxB].second) idxB++;
		else
		{
			rightA = A[idxA].second;
			rightB = B[idxB].second;

			ans.push_back(A[idxA].first);

			idxA++;
			idxB++;
		}
	}
	else if (A[idxA].first > B[idxB].first)
	{
		idxA++;
	}
	else
	{
		idxB++;
	}
}

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N, M;
vector<pair<int,int>> A;
vector<pair<int,int>> B;

bool cmp(pair<int,int> a, pair<int,int> b) 
{
	if (a.first == b.first) return a.second < b.second;
	return a.first > b.first;
}

int main()
{
	INPUT_OPTIMIZE;
	
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		A.push_back({ a, i });
	}

	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int b;
		cin >> b;
		B.push_back({ b, i });
	}

	sort(A.begin(), A.end(), cmp);
	sort(B.begin(), B.end(), cmp);

	int idxA = 0, idxB = 0;
	int rightA = 0, rightB = 0;

	vector<int> ans;
	while (idxA < N && idxB < M)
	{
		if (A[idxA].first == B[idxB].first)
		{
			if (rightA > A[idxA].second) idxA++;
			else if (rightB > B[idxB].second) idxB++;
			else
			{
				rightA = A[idxA].second;
				rightB = B[idxB].second;

				ans.push_back(A[idxA].first);

				idxA++;
				idxB++;
			}
		}
		else if (A[idxA].first > B[idxB].first)
		{
			idxA++;
		}
		else
		{
			idxB++;
		}
	}

	cout << ans.size() << "\n";
	for (auto num : ans)
	{
		cout << num << " ";
	}

	return 0;
}