문자열 S가 주어졌을 때, 글자들을 재배치하여 서로 인접한 두 문자가 같지 않도록 만들 수 있는지 확인하는 문제입니다. 재배치가 가능하다면 가능한 결과 중 하나를 출력하고, 불가능하다면 빈 문자열을 반환해야 합니다. 예를 들어 입력이 "AAB"라면 출력은 "ABA"가 됩니다.
해결 접근 방법
이 문제는 우선순위 큐(priority queue)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 가장 많이 등장한 문자부터 번갈아 배치하는 것입니다. 구체적인 단계는 다음과 같습니다.
- (빈도수, 문자) 형태의 쌍을 저장하는 우선순위 큐 pq와, 문자별 빈도수를 저장할 맵 m을 선언합니다.
- n := 문자열의 길이
- 맵 m에 각 문자의 등장 횟수(빈도수)를 기록합니다.
- m의 모든 키-값 쌍 p에 대해 (빈도수, 문자) 형태로 pq에 삽입합니다.
- ans := 빈 문자열
- pq가 비어 있지 않은 동안 아래 과정을 반복합니다.
- pq의 최상단 원소를 one으로 꺼내고 제거합니다.
- 만약 pq가 비어 있다면:
- one의 빈도수가 1보다 크면 빈 문자열을 반환합니다. (인접 중복 발생)
- 그렇지 않으면 ans에 one의 문자를 추가한 뒤 ans를 반환합니다.
- two := pq의 최상단 원소를 꺼내고 제거합니다.
- ans에 one의 문자와 two의 문자를 차례로 이어 붙입니다.
- one과 two의 빈도수를 각각 1 감소시킵니다.
- 감소 후 빈도수가 0이 아니면 해당 쌍을 다시 pq에 삽입합니다.
- 반복이 끝나면 ans를 반환합니다.
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string reorganizeString(string S) {
priority_queue <pair <int, char>> pq;
map <char, int> m;
int n = S.size();
for(int i = 0; i < n; i++){
m[S[i]]++;
}
map <char, int> :: iterator i = m.begin();
while(i != m.end()){
pq.push({i->second, i->first});
i++;
}
string ans = "";
while(!pq.empty()){
pair <int, char> one = pq.top();
pq.pop();
if(pq.empty()){
if(one.first > 1)
return "";
ans += one.second;
return ans;
}
pair <int, char> two = pq.top();
pq.pop();
ans += one.second;
ans += two.second;
//cout << ans << endl;
one.first--;
two.first--;
if(one.first)pq.push(one);
if(two.first)pq.push(two);
}
return ans;
}
};
int main() {
Solution ob1;
cout << ob1.reorganizeString("AAB") << endl;
return 0;
}입력
S = "AAB"
ob1.reorganizeString("AAB")출력
ABA
동작 원리 요약
"AAB"의 경우 A는 2번, B는 1번 등장하므로 우선순위 큐에는 (2, 'A')와 (1, 'B')가 들어갑니다. 매 반복마다 빈도수가 가장 높은 두 문자를 꺼내 번갈아 배치하고, 남은 개수가 있으면 다시 큐에 넣습니다. 마지막에 한 문자만 남았을 때 그 개수가 1이면 성공, 2 이상이면 어떻게 배치해도 인접 중복이 불가피하므로 빈 문자열을 반환하게 됩니다. 이 방식의 시간 복잡도는 O(n log k)이며, 여기서 n은 문자열 길이, k는 서로 다른 문자의 종류 수입니다.