문제 링크
문자열 a, b가 주어진다.
Kuznecov는 아래의 두 가지의 선택 중 하나를 한 문자열에 포함된 문자가 없어질 때까지 반복한다.
단 둘 중 같은 선택을 k번 이상 연속해서 반복할 수는 없다.
이러한 방법으로 만들 수 있는 문자열 c 중 사전 순으로 가장 빠른 문자열을 구하시오.
사전 순으로 가장 빠른 문자열을 구하는 게 목표기 때문에
이런 방법으로 구현했다.
#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가 시간은 좀 더 오래걸릴 거 같지만 구현이 좀 더 편했으니 만족