백준 1213 팰린드롬 만들기(C++)

* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다

백준 1213 팰린드롬 만들기 입니다

 

문제 해석

이문제 같은경우는 AABB 가 입력이 되었을때 ABBA 로 팰린드롬 문자를 만들고 만약 ABCD같이 팰린드롬이 만들어 지지 않는다면 

I'm Sorry Hansoo 를 출력하면 되는 문제입니다

 

우선 이문제를 풀기위해서는 입력된 문자열에서 각 알파벳(A,B 등등)이 몇개가 쓰였는지 체크를 해봐야됩니다 즉 아래와 같이 카운팅 배열을 이용해야합니다

AABB -> A 2개, B 2개

 

그리고 핵심은 사전순으로 앞서는것부터 출력을 해야되니 알파벳 Z 부터 출력이 됩니다

 

그러면 AABB가 들어왔을때 A는2개이고,B도 2개이니깐 먼저 B부터 배열을 합니다 -> BB

그리고 다음 A2개가 남아있으니 양옆에 A를 붙여줍니다 -> ABBA

 

만약 여기서 ABACABA같이 문자가 하나만 있는 경우가 있다면 최종결과에 한개인 문자(C) 중간에 넣어줍니다 -> AABCBAA

 

이제 여기서 팰린드롬이 안되는 조건을 찾아봐야 되는데 우선 팰린드롬이 안되는 조건은 알파벳 카운팅에서 홀수가 2개이상일 경우 팰린드롬이 만들어지지 않습니다

AB,ABC 와 같이 홀수일경우 팰린드롬을 만드는 조건이 성립이되지 않습니다

 

문제 풀이 순서

1. 입력받을 문자열 과 최종 결과 문자열 변수 선언합니다

2. 알파벳 카운팅 배열과, 홀수 갯수를 체크할 변수를 선언합니다

3. 알파벳이 한개인경우에 넣을 중간값 문자 변수를 선언합니다

4. 문자열을 입력받고 입력받은 문자열 기반으로 카운팅을진행합니다

5. 카운팅 배열을 아스키 코드 역순으로 순회합니다(Z ~ A)

6. 만약 카운팅이 있는경우 우선 홀수를 찾습니다

7. 홀수일경우 홀수가 한개인경우를 생각해 최종 결과 중앙에다 추가할 문자를 찾습니다

8. 그리고 홀수 갯수를 체크할 변수의 값을 증가시키고, 알파벳 카운팅을 하나 뺍니다

9. 만약 홀수 카운팅이 2개일경우 카운팅 배열 순회를 종료합니다

10. 이후 카운팅한 수만큼 순회를 돌며 최종결과 변수에 앞뒤로 문자를 추가합니다

11. 최종 결과 출력하기전 중앙 값이 있다면 최종결과 변수 중앙에 넣어주고, 이후 홀수가 2개일경우 와 아닐경우에 대한 결과를 출력합니다

 

작성 코드

#include<bits/stdc++.h>
using namespace std;
string name,ret;
int arr[26],flag;
char mid;
int main(){
    cin >> name;

    //알파벳 카운팅 배열
    for(int i = 0; i < name.length(); i++){
        arr[name[i] - 'A']++;
    }

    //아스키코드 역순으로 순회
    for(int i = 26; i >= 0;i--){

        //만약 카운팅이 있다면
        if(arr[i]){

            //홀수 찾기 & 1
            if(arr[i] & 1){
                //홀수가 한개가 들어오는 경우,중앙에다 넣을 문자 찾기
                mid = char(i+65);
                flag++;
                arr[i]--;
            }
            //홀수가 2개이상일경우 순회 종료
            if(flag == 2){
                break;
            }
            //아닐경우 알파벳을 카운팅한만큼 순회해서 앞뒤로 붙인다
            for(int j = 0; j < arr[i]; j+=2){
                ret = char(i+65) + ret;
                ret += char(i+65);
            }
        }
        
    }

    //만약 미드 값이 있다면 최종결과 중간에 넣는다
    if(mid){
        ret.insert(ret.begin() + ret.size() / 2,mid);
    }

    //홀수가 2개일경우, sry, 아닐결우 최종 결과 출력
    if(flag == 2){
        cout << "I'm Sorry Hansoo" << "\n";
    }else{
        cout << ret << "\n";
    }
    
    return 0;
}