[ 백준 ] 1213 / 팰린드롬 만들기

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
47/228
post-thumbnail

# Appreciation

/*
 * Problem :: 1213 / 팰린드롬 만들기
 *
 * Kind :: Simulation
 *
 * Insight
 * - 팰린드롬을 만드려면
 *   각 알파벳 문자가 등장한 횟수들에서
 *   홀수인 문자의 개수가 1개 이하여야 한다
 *   + 사전순으로 앞서는 팰린드롬을 만들어야 하므로
 *     A 부터 Z 까지 순회해 주자
 *
 * Point
 * - 팰린드롬 S를
 *   F(앞 부분) + M(가운데 부분) + B(뒷 부분)
 *   로 나누어서 생각해주자
 *   여기서 B 는 F 를 뒤집은 문자열이며
 *   M 은 길이 0 또는 1 의 문자열이다
 *   + 길이 홀수인 S = F + M + B
 *     길이 짝수인 S = F + B
 *     # M 에는 등장횟수가 홀수인 알파벳 문자가 들어가며
 *       길이 2 초과시 주어진 문자열로 팰린드롬을 만들 수 없음을 뜻하게 된다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    string S; cin >> S;

    // Process
    int C[26] = {0, }; /* 알파벳의 등장횟수 저장 */
    for (char c : S) {
        C[c-'A']++;
    }

    string M; /* 팰린드롬 가운데 부분 */
    for (int i=0; i<26; i++) {
        if (C[i]%2 == 1) { /* 알파벳의 등장횟수가 홀수라면 */
            M.push_back('A'+i); /* M 에 추가 */
        }
    }

    string A;
    /* M 의 길이가 1 이하인 경우에만 팰린드롬을 만들 수 있음 */
    if (M.length() <= 1) {
        string F; /* 팰린드롬 앞 부분 */
        for (int i=0; i<26; i++) {
            F += string(C[i]/2, 'A'+i);
        } string B(F.rbegin(), F.rend()); /* 팰린드롬 뒷 부분 */
        A = F + M + B;
    }

    // Control : Output
    if (M.length() > 1)
        cout << "I'm Sorry Hansoo" << endl;
    else
        cout << A << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글