[BOJ C++] 백준 30805번: 사전 순 최대 공통 부분 수열

 📚 문제

[BOJ C++] 백준 30805번: 사전 순 최대 공통 부분 수열
https://www.acmicpc.net/problem/30805

 

---

 📝 입력 및 출력

---

 🔎 문제 풀이

• 처음에는 먼저 LCS를 구한 후, 그 안에서 비오름차순을 만족하면서 사전 순으로 나중인 수열을 찾으려고 했다. 그러나 사전 순으로 가장 나중에 있는 수열이 꼭 LCS에 포함되어 있다는 보장이 없기 때문에 이 방식은 잘못되었다.
• 다음으로는 반복문을 돌며 두 수열에 공통인 숫자가 있을 때 결과 배열(rst)에 추가하는 방식으로 구현하였다. rst 배열은 사전 순으로 가장 나중인 수열이어야 하므로 rst 배열에 새로운 수를 삽입할 때는 기존에 이미 입력된 수보다 작거나 같아지는 위치에 삽입할 수 있다.
• 예를 들어, rst 배열이 {9, 8, 2, 1}이고, 5를 삽입한다고 하면, 2 대신 5를 삽입하여 {9, 8, 5}와 같은 모양으로 만들면 된다. 그러나 이 방식이 항상 맞으려면 8이 5보다 앞에 있던 수여야 한다. 두 수열이 {3, 9, 8, 2, 1, 5, 1}, {9, 5, 8, 1, 2, 1} 과 같은 형태라면, 5가 공통된 수 이므로 rst배열에 삽입하지만, 사실 두 번째 수열의 8 보다 앞에 있는 수 이므로 삽입할 수 없다는 것이다. 따라서 이런 문제를 방지하기 위해 이미 삽입한 수의 인덱스 또한 따로 저장해야한다.
• 즉, rst 배열과 idx 배열을 두어 이미 삽입된 수의 인덱스를 함께 관리한다. 또, 사전 순으로 나중인 배열을 만들기 위해 이미 삽입된 수를 덮어쓰면 배열의 크기가 변하기 때문에 변수 len을 두어 수열의 길이를 저장하는 방식으로 구현하였다. 

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

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

    int n, m, len = 0;
    cin >> n;
    vector<int> rst(101);
    vector<int> idx(101);
    idx[0] = -1;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> m;
    vector<int> b(m);
    for (int i = 0; i < m; i++) cin >> b[i];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int k = 1;
            if (a[i] == b[j]) {
                while (b[j] <= rst[k] && k <= len) k++;
                if (idx[k - 1] < j) {
                    idx[k] = j;
                    rst[k] = b[j];
                    len = k;
                    break;
                }
            }
        }
    }
    cout << len << '\n';
    for (int i = 1; i <= len; i++) cout << rst[i] << ' ';
}