문제 개요
비어 있지 않은 문자열 s와 정수 k가 주어졌을 때, 같은 문자끼리 서로 최소 k만큼 거리를 유지하도록 문자열을 재정렬해야 합니다. 문자열은 소문자로만 구성되어 있으며, 조건을 만족하는 재정렬이 불가능한 경우에는 빈 문자열을 반환합니다.
예를 들어 s = "aabbcc", k = 3이 입력으로 주어지면 정답 중 하나는 "abcabc"입니다. 동일한 문자가 이전에 등장한 위치와 최소 3칸 이상 떨어져 있기 때문입니다. 조건만 충족한다면 여러 가지 정답이 허용되며, 아래 코드의 실행 결과는 "bacbac"입니다.
알고리즘 접근 방식
이 문제는 우선순위 큐(priority queue)와 덱(deque)을 함께 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "남은 개수가 많은 문자를 우선적으로 배치하되, 최근 k개 안에 사용된 문자는 잠시 대기시킨다"는 것입니다. 구체적인 단계는 다음과 같습니다.
- 문자 빈도 계산: 해시 맵(unordered_map)을 이용해 문자열의 각 문자가 몇 번 등장하는지 셉니다.
- 우선순위 큐 구성: (문자, 남은 개수) 쌍을 만들어, 개수가 많은 문자가 먼저 나오도록 하는 우선순위 큐(최대 힙)에 모두 삽입합니다.
- 문자 배치: 큐에서 가장 개수가 많은 문자를 꺼내 결과 문자열 ret 뒤에 붙이고, 남은 개수를 1 감소시킨 뒤 덱 dq의 뒤쪽에 임시 보관합니다.
- k 거리 제한 관리: 덱의 크기가 k 이상이 되면 맨 앞의 원소를 꺼냅니다. 이 문자는 마지막으로 사용된 지 이미 k칸 이상 지났으므로, 남은 개수가 0보다 크다면 다시 우선순위 큐에 넣어 재사용할 수 있습니다.
- 결과 판정: 반복이 끝난 후 덱 앞쪽에서 남은 개수가 0인 원소들을 제거합니다. 그래도 덱에 원소가 남아 있다면 배치하지 못한 문자가 있다는 뜻이므로 빈 문자열을 반환하고, 덱이 비어 있다면 완성된 ret을 반환합니다.
C++ 구현 예제
아래 코드는 위 알고리즘을 C++로 구현한 것입니다. Comparator 구조체는 두 쌍을 비교하여 남은 개수가 많은 문자가 항상 우선순위 큐의 top에 위치하도록 합니다.
#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);
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
b, a, c 각 문자가 이전 등장 위치와 최소 3칸씩 떨어져 있으므로 문제의 조건을 만족하는 올바른 정답입니다.
복잡도 분석
문자열 길이를 n, 서로 다른 문자의 개수를 m이라고 할 때, 문자 하나를 배치할 때마다 우선순위 큐에 한 번의 삽입 또는 삭제가 일어나므로 시간 복잡도는 O(n log m)입니다. 공간 복잡도는 해시 맵, 덱, 결과 문자열을 포함하여 O(n)입니다. 다룰 수 있는 문자가 알파벳 소문자 26개로 제한되므로 사실상 선형 시간에 동작합니다.