[BOJ] 30805 - 사전 순 최대 공통 부분 수열

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

BOJ - 사전 순 최대 공통 부분 수열

문제 유형: 그리디, 정렬

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 1024MB

 

문제

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

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

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

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

양의 정수로 이루어진 길이가 N인 수열 {A1,⋯,AN}이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 M인 수열 {B1,⋯,BM}이 주어집니다.

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

 

입력

첫 줄에 수열 A의 길이 N이 주어집니다. (1≤N≤100)

둘째 줄에 N개의 양의 정수 A1,A2,⋯,AN이 주어집니다. (1≤Ai≤100)

셋째 줄에 수열 B의 길이 M이 주어집니다. (1≤M≤100)

넷째 줄에 M개의 양의 정수 B1,B2,⋯,BM이 주어집니다. (1≤Bi≤100)

 

출력

 A와 B의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 크기 K$K$를 출력하세요.

 K≠0이라면, 다음 줄에 K개의 수를 공백으로 구분해 출력하세요. i번째 수는 A와 B의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 i번째 수입니다.

 

풀이

정답은 공통의 부분 요소들의 시퀀스에서 가장 큰 요소를 포함한 가장 긴 감소하는 부분 순열이다.

 

그를 구하는 방법은 아래와 같다:

a와 b에 대해서 각각 {수, 인덱스}로 저장한다.

그리고, 수에 대해서 내림차순 정렬, 인덱스 기준 오름차순 정렬한다.

그러고 각각의 {수, 인덱스 쌍}을 확인하면서, 조건에 맞으면 수를 추가하며 늘려나가면 된다.

 

최종 결과를 반환한다.

 

코드

C++

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

int n, m;

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

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  vector<pair<int, int>> a, b;
  int temp;

  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> temp;
    a.push_back({temp, i});
  }

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

  sort(a.begin(), a.end(), comp());
  sort(b.begin(), b.end(), comp());

  vector<int> ans;
  int ai = 0, bi = 0;
  int alimit = -1, blimit = -1;
  while (ai < n && bi < m) {
    if (a[ai].first == b[bi].first) {
      if (a[ai].second < alimit)
        ai++;
      else if (b[bi].second < blimit)
        bi++;
      else {
        ans.push_back(a[ai].first);
        alimit = a[ai].second;
        blimit = b[bi].second;
        ai++;
        bi++;
      }
    } else if (a[ai].first > b[bi].first) {
      ai++;
    } else {
      bi++;
    }
  }

    
  cout << ans.size() << "\n";
  for (int x : ans) {
    cout << x << " ";
  }
  cout << "\n";

  return 0;
}