C++에서 문자열을 재배열해 회문(Palindrome) 만들기

임의의 길이를 가진 문자열 'str'이 주어졌을 때, 주어진 입력 문자열에서 문자를 추가하거나 제거하지 않고 문자들을 재배열하여 출력 결과가 회문(palindrome) 문자열이 되도록 하는 것이 과제입니다. 회문 문자열은 앞에서 읽으나 뒤에서 읽으나 동일하게 발음되는 문자 배열을 가진 문자열을 의미합니다.

입력 및 출력 시나리오 살펴보기

입력 − string str = "itnin"

출력 − 회문 형성이 가능한 경우 문자 재배열 결과: nitin

설명 − 문자열 타입 변수 str이 주어집니다. 이제 입력 문자열의 문자들을 회문 문자열이 되도록 재배열하고, 불가능한 경우 'NOT POSSIBLE'을 반환합니다. 따라서 주어진 입력 문자열에 대한 출력은 'nitin'입니다.

입력 − string str = "baaaba"

출력 − 회문 형성이 가능한 경우 문자 재배열 결과: aabbaa

설명 − 문자열 타입 변수 str이 주어집니다. 입력 문자열의 문자들을 회문이 되도록 재배열하며, 불가능한 경우 'NOT POSSIBLE'을 반환합니다. 따라서 주어진 입력 문자열에 대한 출력은 'aabbaa'입니다.

프로그램에 사용된 접근 방식

string 타입 변수(예: str)를 입력받고, 문자열의 크기를 계산하여 length라는 변수에 저장합니다.
데이터를 Rearrangement(str, length) 함수에 전달합니다.
Rearrangement(arr, length) 함수 내부에서 다음 작업을 수행합니다.
- char와 int 쌍을 저장하는 unordered_map 타입 변수 'um'을 생성합니다.
- 정수형 변수 total을 선언하고 0으로 초기화합니다.
- 문자형 변수 'ch'와 문자열 타입 변수 str_1, str_2를 생성합니다.
- i가 0부터 length보다 작을 때까지 FOR 루프를 시작합니다. 루프 안에서 um[str[i]] 값을 1씩 증가시켜 각 문자의 등장 횟수를 계산합니다.
- 맵 'um'을 순회하는 FOR 루프를 시작합니다. 루프 안에서 it.second % 2가 0이 아닌지 확인하고, 홀수 개수인 문자가 있다면 total을 1 증가시키고 ch에 해당 문자(it.first)를 저장합니다.
- total이 1보다 크거나, total이 1이면서 문자열 길이가 짝수(length % 2 == 0)인 경우 0을 반환합니다. 이는 회문 생성이 불가능함을 의미합니다.
- 맵 'um'을 순회하는 FOR 루프를 시작합니다. 루프 안에서 string(it.second / 2, it.first)으로 각 문자의 절반만큼의 문자열을 만들고, str_1에는 뒤에 추가하고 str_2에는 앞에 추가합니다.
- total이 1이면 str_1 + ch + str_2를 반환하고, 그렇지 않으면 str_1 + str_2를 반환합니다.
결과를 출력합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
string Rearrangement(string str, int length){
    unordered_map<char, int> um;
    int total = 0;
    char ch;
    string str_1 = "";
    string str_2 = "";

    for (int i = 0; i < length; i++){
        um[str[i]]++;
    }
    for(auto it : um){
        if(it.second % 2 != 0){
            total++;
            ch = it.first;
        }
    }
    if(total > 1 || total == 1 && length % 2 == 0){
        return 0;
    }
    for(auto it : um){
        string str(it.second / 2, it.first);
        str_1 = str_1 + str;
        str_2 = str + str_2;
    }
    if(total == 1){
        return str_1 + ch + str_2;
    }
    else{
        return str_1 + str_2;
    }
}
int main(){
    string str = "itnin";
    int length = str.size();
    cout<<"Rearrangement of characters to form palindrome if possible is: "<<Rearrangement(str, length);
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Rearrangement of characters to form palindrome if possible is: nitin

핵심 원리 정리

이 알고리즘의 핵심은 회문의 성질을 활용하는 것입니다. 회문이 되려면 모든 문자가 짝수 번 나타나야 하며, 문자열 길이가 홀수인 경우 단 하나의 문자만 홀수 번 나타날 수 있습니다(이 문자는 중앙에 위치). unordered_map으로 각 문자의 빈도를 계산한 후, 조건을 만족하면 각 문자의 절반을 좌우 대칭으로 배치하여 회문을 구성합니다. 시간 복잡도는 O(n)으로 매우 효율적입니다.