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

 

 구현 문제다. 그리디나 완전 탐색이라고 생각해도 될 것 같다. N과 M의 범위가 상당히 작기 때문에 어떻게 풀어도 풀린다. 처음엔 DP스럽게 접근하려고 배열만 이용해서 풀었는데, 조건 처리가 많아서 지저분해 보이는 것이 마음에 안 들었다.

 

 원리는 간단한데, 핵심 부분은 O(n^2)인 LCS 알고리즘과 유사하다. 배열 A를 선형 탐색하는 루프 내에서 배열 B를 선형 탐색한다. 이때, 값이 일치하는 경우를 찾았다면 lcs 배열을 앞에서부터 선형 탐색하며, 현재 일치하는 값보다 작은 배열 원소가 있는지 확인한다. 그런 원소가 있다면 현재 일치하는 값으로 갱신해 주고, 아니라면 lcs 배열 끝에 붙일 수 있는지 확인해서(마지막 원소에서 사용한 배열 B 인덱스보다 현재 일치된 값을 가지는 배열 B 인덱스가 큰 경우) 붙여준다.

 O(n^3)짜리 알고리즘이고, 문제 조건에서 충분히 가능하다. 그런데 루프의 구조 상, 현재 탐색 중인 배열 A 인덱스가 현재까지 만들어진 lcs 배열의 원소들보다 무조건 뒤에 있음만 확정할 수 있고, 나머지 부분은 조건 처리를 걸어 확인해야 하므로 조금 지저분해진다.

 

#include <iostream>

using namespace std;

int arrA[101];
int arrB[101];
int lcs[101];

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

    int n, m;

    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> arrA[i];
    }
    cin >> m;
    for(int i=1; i<=m; i++) {
        cin >> arrB[i];
    }

    lcs[0] = 0;
    int lcsInd = 0;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(arrA[i]==arrB[j]) {
                if(lcsInd==0) {
                    lcs[1] = j;
                    lcsInd = 1;
                    break;
                } else {
                    int pos = lcsInd+1;
                    for(int k=1; k<=lcsInd; k++) {
                        if(arrB[lcs[k]]<arrA[i] && lcs[k-1]<j) {
                            pos = k;
                            break;
                        }
                    }
                    if((pos==lcsInd+1 && lcs[lcsInd]<j) || pos!=lcsInd+1) {
                        lcs[pos] = j;
                        lcsInd = pos;
                        break;
                    }
                }
            }
        }
    }

    cout << lcsInd << "\n";
    for(int i=1; i<=lcsInd; i++) {
        cout << arrB[lcs[i]] << " ";
    }
}

 

 

 

 그래서 조금 생각하다가, 우선순위 큐를 도입해서 푸는 방법으로 새로 풀었다.

 

 배열 B는 그대로 두고, 배열 A 대신에 A의 원소들을 우선순위 큐에 담았다. 우선순위는 값이 클수록, 값이 같다면 등장 인덱스가 작을수록 크다.

 이렇게 하면 우선순위 큐를 pop() 하면서 이용하는 루프 내에서, 현재 top의 원소가 lcs를 구성하고 남은 A의 원소들 중 가장 크거나 같은 값임을 보장할 수 있다. 대신에 lcs에 이용된 값보다 현재 top 값의 인덱스가 더 뒤에 위치한다는 것은 보장할 수가 없으므로(엄밀하게는 lcs 내의 같은 값들보다는 뒤에 있음을 보장할 순 있다), 우선순위 큐 내에 값과 함께 기존 A 배열 상에서의 인덱스 값을 같이 담아서 이를 처리할 수 있게 해 두었다.

 이제 남은 건, 그렇게 적합한 A값을 뽑은 상태에서 배열 B 내에 해당 값이 있는지 찾아주기만 하면 된다. 배열 B를 앞에서부터 선형 탐색하며 일치하는 값을 찾는데, 나는 bStartInd 라는 값을 두고 배열 B의 시작점을 정해주었다. 만약 일치하는 값을 찾으면, 다음 탐색부터는 배열 B 내에서 해당 인덱스까지는 더 이상 찾아볼 이유가 없으므로, bStartInd 값을 찾아낸 인덱스+1로 갱신해 주고 lcs에 값을 추가해 주었다. 

 

 이렇게 하니까 코드가 더 깔끔해 보였고, 성능 상으로도 O(n^2 log n)이므로 더 우위에 있어 만족스러웠다.

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int arrB[101];

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

    int n, m, num;

    priority_queue<pair<int, int> > pqA;

    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> num;
        pqA.push({num, -i});
    }
    cin >> m;
    for(int i=1; i<=m; i++) {
        cin >> arrB[i];
    }

    vector<pair<int, int> > lcs; // {num, aInd}
    int bStartInd = 1;

    while(!pqA.empty()) {
        int topNum = pqA.top().first;
        int topInd = -pqA.top().second;
        pqA.pop();

        if(!lcs.empty() && lcs[lcs.size()-1].second>topInd) continue;

        for(int i=bStartInd; i<=m; i++) {
            if(topNum == arrB[i]) {
                lcs.push_back({topNum, topInd});
                bStartInd = i+1;
                break;
            }
        }
    }

    cout << lcs.size() << "\n";
    for(auto p: lcs) {
        cout << p.first << " ";
    }

}