C++에서 문자열 재구성

문자열 S가 있다고 가정하고 서로 인접한 두 문자가 동일하지 않도록 문자를 재배열할 수 있는지 확인합니다. 가능한 경우 가능한 결과를 출력하십시오. 이것이 불가능하면 빈 문자열을 반환합니다. 따라서 입력이 "AAB"와 같으면 출력은 "ABA"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• pq라는 정수 문자 쌍의 우선 순위 큐를 만들고 하나의 맵 m을 정의합니다.
• n :=문자열의 크기
• 맵 m에 문자 빈도 저장
• m
  의 각 키-값 쌍 p에 대해
  • 삽입(p의 정수 부분, p의 문자 부분)
• ans :=빈 문자열
• pq가 비어 있지 않은 동안
  • 1 :=pq에서 상위 쌍을 설정하고 pq에서 상위 쌍을 삭제합니다.
  • pq가 비어 있으면
    • 1의 정수 부분> 1이면 빈 문자열을 반환합니다.
    • ans :=as + 하나의 문자 부분
    • 반환
  • two :=pq에서 최상위 쌍, pq에서 최상위 쌍 삭제
  • ans :=as + 하나의 문자 부분
  • ans :=ans + 2의 문자 부분
  • 1과 2의 정수 부분을 1씩 증가
  • 1의 정수 부분이 0이 아니면 pq에 1을 삽입
  • 2의 정수 부분이 0이 아니면 pq에 1을 삽입
• 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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