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

1. 문제 풀이

 배열을 { 값, 순서 } 형태로 저장합니다. 여기서 값은 배열의 실제 값이고, 순서는 해당 값이 배열에서 등장한 순서를 의미합니다. 이 배열을 값을 기준으로 내림차순으로 정렬하되, 값이 같다면 순서를 오름차순으로 정렬합니다.

 정렬한 두 배열의 처음 값을 가리키는 포인터를 각각 두고, 두 포인터 중 하나가 배열의 끝에 도달할 때까지 비교를 진행합니다. 두 포인터가 가리키는 값 중 더 큰 값을 가진 포인터를 앞으로 이동시킵니다. 과정을 진행하다가 두 포인터가 가르키는 값이 서로 같아지면 해당 값이 지금까지 저장한 부분 수열의 마지막 값의 순서보다 나중에 등장한 값이라면 그 값을 부분 수열에 추가합니다. 그렇지 않다면 버리고, 계속 진행합니다.

 여기서 중요한 점은, 부분 수열에 값을 추가할 때 단순히 값을 저장하는 것이 아니라, 해당 값과 그 값이 등장한 두 배열에서의 순서쌍도 함께 저장해야 합니다. 즉,  { 값, 배열 A에서의 순서, 배열 B에서의 순서 } 형태로 저장해야 합니다. 그리고 포인터의 값이 같으나 지금까지 저장한 부분 수열의 마지막 값 순서보다 빠르다면, 두 포인터 중 순서가 더 빠른 포인터만 앞으로 이동시킵니다.

 

위 과정을 따라가면 두 수열에서 사전 순으로 가장 마지막에 등장하는 최대 공통 수열을 그리디하게 구할 수 있습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, m;
vpi a, b;


bool cmp(const pi &a, const pi &b){
  return (a.X == b.X ? a.Y < b.Y : a.X > b.X);
}


int main() {
  fastio(nullptr, false);
  
  // input
  cin >> n;
  for(int i = 0; i < n; i++){
    int val;
    cin >> val;
    a.pb({val, i});
  }

  cin >> m;
  for(int i = 0; i < m; i++){
    int val;
    cin >> val;
    b.pb({val, i});
  }

  // init
  sort(all(a), cmp);
  sort(all(b), cmp);

  // solve
  auto a_it = a.begin();
  auto b_it = b.begin();
  vti ans;
  while(a_it < a.end() || b_it < b.end()){
    auto curA = *a_it;
    auto curB = *b_it;
    if(curA.X == curB.X){
      if(ans.empty() || ( get<1>(ans.back()) < curA.Y && get<2>(ans.back()) < curB.Y)){
        ans.pb({curA.X, curA.Y, curB.Y});
        a_it++; b_it++;
      }
      else{
        if(get<1>(ans.back()) > curA.Y) a_it++;
        if(get<2>(ans.back()) > curB.Y) b_it++;
      }
    }
    else if(curA.X > curB.X) a_it++;
    else b_it++;
  }

  // output
  cout << sz(ans) << nl;
  for(auto &cur : ans){
    cout << get<0>(cur) << ' ';
  }
}

 

3. 제출 결과