[Baekjoon] 30805번: 사전 순 최대 공통 부분 수열

🥅 문제

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

 

🔍 설계

사전 순으롤 가장 뒤에 있는 공통 부분 수열을 찾으면 되므로, 먼저 각 수열을 큰 수가 앞에 오도록, 수의 크기가 같다면, 인덱스가 작은 것이 앞에 오도록 하게 하기 위해 우선순위 큐를 이용하였다. 

 

각각의 우선순위 큐에서 앞에 있는 하나를 꺼내면서 같다면, 결과에 추가한다.

다르다면, 큰 것이 있는 우선순위 큐에서 하나를 없앤다. 큰 것이 계속 남아있다면, 그와 같은 것이 다른 쪽에 없기 때문이다.

 

주의해야할 것은 크기 뿐만 아니라 결과에 포함되는 수가 각각 양쪽 수열에서 어느 인덱스에 위치하는 지를 기록하고, 그 인덱스보다 작다면 결과에 추가될 수 없으므로 없애는 과정이 포함되어야 한다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m, number, limit_a_idx = 0, limit_b_idx = 0;

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

priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq1;
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq2;
vector<int> result;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> number;
		pq1.push({ number, i });
	}

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> number;
		pq2.push({ number, i });
	}

	while (!pq1.empty() && !pq2.empty()) {
		if (!pq1.empty() && pq1.top().second < limit_a_idx) {
			pq1.pop();
			continue;
		}
		if (!pq2.empty() && pq2.top().second < limit_b_idx) {
			pq2.pop();
			continue;
		}

		if (pq1.top().first == pq2.top().first) {
			result.push_back(pq1.top().first);
			limit_a_idx = pq1.top().second;
			limit_b_idx = pq2.top().second;
			pq1.pop();
			pq2.pop();
		}
		else if (pq1.top().first > pq2.top().first) {
			pq1.pop();
		}
		else if (pq1.top().first < pq2.top().first) {
			pq2.pop();
		}
	}

	int size = result.size();

	cout << size << "\n";

	for (int i = 0; i < size; i++) {
		cout << result[i] << " ";
	}

	return 0;
}