비어 있지 않은 문자열 s와 정수 k가 있다고 가정합니다. 동일한 문자가 서로 최소 거리 k가 되도록 문자열을 재배열해야 합니다. 주어진 문자열은 소문자입니다. 문자열을 재정렬할 방법이 없으면 빈 문자열이 됩니다.
따라서 입력이 s ="aabbcc", k =3과 같으면 출력은 "abcabc"가 됩니다. 이는 동일한 문자가 서로 최소 거리 3이기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ret :=빈 문자열
-
하나의 맵 정의
-
n :=s
의 크기 -
initialize i :=0의 경우, i
-
(m[s[i]] 1씩 증가)
-
-
하나의 우선순위 큐 pq 정의
-
m 단위의 각 키-값 쌍에 대해 다음을 수행합니다. -
-
temp :=키와 값이 있는 쌍
-
pq에 temp 삽입
-
(1씩 증가)
-
-
하나의 데크 dq 정의
-
동안(pq가 비어 있지 않음) −
-
curr :=pq의 맨 위
-
pq에서 요소 삭제
-
ret :=ret + curr.first
-
(curr.second를 1씩 감소)
-
dq의 끝에 curr 삽입
-
dq의 크기>=k인 경우 -
-
curr :=dq의 첫 번째 요소
-
dq에서 앞 요소 삭제
-
curr.second> 0이면 -
-
pq에 curr 삽입
-
-
-
-
동안 (dq가 비어 있지 않고 dq의 첫 번째 요소가 0과 동일하지 않음) −
-
dq에서 앞 요소 삭제
-
-
반환(dq가 비어 있으면 ret, 그렇지 않으면 공백 문자열)
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
struct Comparator {
bool operator()(pair<char, int> a, pair<char, int> b) {
return !(a.second > b.second);
}
};
class Solution {
public:
string rearrangeString(string s, int k) {
string ret = "";
unordered_map<char, int> m;
int n = s.size();
for (int i = 0; i < n; i++) {
m[s[i]]++;
}
unordered_map<char, int>::iterator it = m.begin();
priority_queue<pair<char, int<, vector<pair<char, int>>,
Comparator> pq;
while (it != m.end()) {
pair<char, int> temp = {it->first, it->second};
pq.push(temp);
it++;
}
deque<pair<char, int>> dq;
while (!pq.empty()) {
pair<char, int> curr = pq.top();
pq.pop();
ret += curr.first;
curr.second--;
dq.push_back(curr);
// cout << ret << " " << dq.size() << endl;
if (dq.size() >= k) {
curr = dq.front();
dq.pop_front();
if (curr.second > 0)
pq.push(curr);
}
}
while (!dq.empty() && dq.front().second == 0)
dq.pop_front();
return dq.empty() ? ret : "";
}
};
main() {
Solution ob;
cout << (ob.rearrangeString("aabbcc", 3));
} 입력
"aabbcc", 3
출력
bacbac