[Codeforces #798] A. Lex String

tolelom·2022년 6월 26일
0

코드포스

목록 보기
2/4

문제 설명

문제 링크
문자열 a, b가 주어진다.
Kuznecov는 아래의 두 가지의 선택 중 하나를 한 문자열에 포함된 문자가 없어질 때까지 반복한다.

  1. a에서 아무 문자를 선택해 a에서 지우고 c의 뒤에 추가한다.
  2. b에서 아무 문자를 선택해 b에서 지우고 c의 뒤에 추가한다.

단 둘 중 같은 선택을 k번 이상 연속해서 반복할 수는 없다.

이러한 방법으로 만들 수 있는 문자열 c 중 사전 순으로 가장 빠른 문자열을 구하시오.

알고리즘

사전 순으로 가장 빠른 문자열을 구하는 게 목표기 때문에

  1. a와 b에 속한 문자열을 사전 순으로 정렬한다.
  2. 두 가지의 선택 중 어떤 선택을 할지 정한다.
    2-1. 이때까지 같은 선택을 k번 반복했다면 다른 선택을 한다.(강제)
    2-2. a와 b에 남아있는 문자 중 가장 사전 순으로 빠른 문자를 서로 비교한 후 사전 순으로 빠른 문자를 빼서 c에 넣는다.
  3. 선택에서 이전과 다른 선택을 하면 카운트를 초기화한다.
  4. 해당 선택이 몇 번 연속 반복되었는지 카운트한다.
  5. 2번으로 되돌아 간다.

이런 방법으로 구현했다.

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
 
int tc;
int n, m, k;
string a, b;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> tc;
 
    for (int tcCnt = 1; tcCnt <= tc; ++tcCnt) {
        cin >> n >> m >> k;
        cin >> a >> b;
 
        priority_queue<char, vector<char>, greater<char>> aPq, bPq;
        for (auto chr : a)
            aPq.push(chr);
        for (auto chr : b)
            bPq.push(chr);
 
 
        string ans = "";
        int cnt = 0;
        bool beforeATurn = true;
        while (!aPq.empty() && !bPq.empty()) {
            bool nowATurn = true;
            if (cnt == k) {
                nowATurn = !beforeATurn; cnt = 0;
            } else {
                nowATurn = (aPq.top() < bPq.top());
                if (beforeATurn != nowATurn) cnt = 0;
            }
 
            if (nowATurn) {
                ans += aPq.top(); aPq.pop();
            } else {
                ans += bPq.top(); bPq.pop();
            }
            cnt++;
            beforeATurn = nowATurn;
        }
        cout << ans << '\n';
    }
}

느낀 점...

이 글을 쓰면서 생각난 건데 priority queue를 사용하지 않고 vector에 저장한 다음 sort해서 index를 가리키면서 진행해도 상관 없었을 거 같다.
priority queue가 시간은 좀 더 오래걸릴 거 같지만 구현이 좀 더 편했으니 만족

profile
이것 저것 작성하는 기술 블로그

0개의 댓글