백준 1213번 : 팰린드롬 만들기

문제링크 :https://www.acmicpc.net/problem/1213

1213번: 팰린드롬 만들기

 

 문제설명 

 

1. 첫째줄에 알파벳 대문자로 이루어진 문자열이 주어진다.

2. 그 문자열로 팰린드롬을 만들 수 있으면 팰린드롬을 출력하고

3. 만들 수 없으면 I'm Sorry Hansoo 를 출력한다.

 

 알고리즘 

 

1. 주어진 문자열에서 알파벳 갯수를 세어주고 

2. 갯수가 홀수인 알파벳이 2개이상이면 팰린드롬을 만들 수없으므로 I'm Sorry Hansoo 를 출력

3. 그다음 'A' 부터 알파벳 갯수의 1/2 을 먼저 출력하고 갯수가 홀수인 알파벳을 가장 마지막에 출력.

4. 그다음 다시 'Z' 부터 남은 알파벳 갯수 1/2을 출력 한다.

 

 

 코드 

 

#include<iostream>
#include<algorithm>
#include<string>
 
using namespace std;
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(0);
 
    string s;
 
    int arr[26],cnt=0,idx=-1;
 
    
    cin >> s;
    
    //알파벳 갯수 배열 초기화
    for (int i = 0; i < 26; i++)arr[i] = 0;
 
    //알파벳 갯수세기
    for (int i = 0; i < s.size(); i++) {
        arr[s[i] - 'A']++;
    }
    
    for (int i = 0; i < 26; i++) {
        //알파벳 갯수가 홀수
        if (arr[i] % 2 == 1) {
            cnt++;
            idx = i;
        }
 
    }
 
    //갯수가 홀수개인 알파벳의 수가 2개이상이면 팰린드롬을 만들 수없음
    if (cnt > 1) {
        cout << "I'm Sorry Hansoo";
        return 0;
    }
 
    string answer = "";
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < arr[i] / 2; j++) {
            answer.push_back('A' + i);
        }
    }
 
    if(idx!=-1)
    answer.push_back('A' + idx);
 
    for (int i = 25; i >= 0; i--) {
 
        for (int j = 0; j < arr[i] / 2; j++) {
            answer.push_back('A' + i);
        }
    }
 
    cout << answer;
 
}