[BOJ S3][C++] 백준 1213번: 팰린드롬 만들기

https://www.acmicpc.net/problem/1213

1213번: 팰린드롬 만들기

 

문제

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

입력

첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

 

풀이

문자열을 받아서 해당 문자열에 들어간 알파벳의 개수를 세어서 alphabet[] 배열에 넣어준다.

 

이제 세가지 갈림길

1. 모든 알파벳이 짝수개수

2. 한개의 알파벳이 홀수개수, 나머지는 짝수개수

3. 두개 이상의 알파벳이 홀수개수

 

1번은 그냥 구현하면된다.

2번은 홀수개수인 알파벳이 센터에 쓰이면 된다

3번은 구현이 불가능하다 -> sorry 어쩌구

 

구현은 더 간단하다. 어차피 사전순이므로 alphabet 배열을 돌며 앞에것부터

개수의 절반만큼을 halfAns 문자열에 추가

 

정답인 문자열은 {halfAns} + {센터알파벳 (있다면)} + {halfAns 거꾸리버전}

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

string solution(string s) {
    string ans;
    
    // 문자열에 들어간 알파벳 갯수 세기
    vector<int> alphabet(26, 0);
    for(int i=0; i<s.size(); i++)
        alphabet[s[i]-'A']++;
    
    // 개수가 홀수인 알파벳 카운트하기
    int odd = -1;
    for(int i=0; i<26; i++) {
        if(alphabet[i] % 2 == 1) { // 홀수 개수인 알파벳이 있다면
            if(odd != -1) return "I'm Sorry Hansoo";  // 이미 홀수 개수인 알파벳이 있을 경우
            odd = i;  //  홀수 개수인 알파벳 보관
        }
    }
    
    // 답 문자열 반쪽 구하기
    string halfAns;
    for(int i=0; i<26; i++) {
        for(int j=0; j<alphabet[i]/2; j++) {
            halfAns.push_back(i+'A');
        }
    }
    
    // 구한 반쪽문자열 추가하고, 센터에 알파벳(있다면) 넣고, 반쪽문자열 뒤집어서 추가
    ans += halfAns;
    
    if(odd != -1) ans.push_back(odd+'A');
    
    reverse(halfAns.begin(), halfAns.end());
    ans += halfAns;
    
    return ans;
}

int main() {
    string input;
    cin >> input;

    string ans = solution(input);
    
    cout << ans;
    
    return 0;
}

/*
 */