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

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

1213번: 팰린드롬 만들기

주어진 알파벳으로 펠린드롬을 만들 수 있는지 물어보는 문제입니다.

 

먼저 펠린드롬을 만들 때 2가지 경우가 있는데 단어 수가 짝수일 때와 홀수일 때 조건이 다릅니다.

 

1. 단어 수가 짝수일 때

-> '홀수'개의 알파벳이 존재하면 안됩니다.

2. 단어 수가 홀수일 때

-> '홀수'개의 알파벳이 2개 이상 존재하면 안됩니다.

 

1번의 경우는 간단합니다.

예를 들어, AABBCD로 총 6개의 알파벳으로 펠린드롬을 만든다고 할 때,

다음과 같이 홀수개의 알파벳이 존재하면 펠린드롬을 만들 수 없습니다.

 

2번의 경우도 확인해보면

AAABBBCCDDE로 11개의 알파벳으로 펠린드롬을 만든다고 할 때,

이를 펠린드롬으로 만들 수 없습니다.

하지만 AAABBCCDDEE로 11개의 알파벳이지만 홀수개의 알파벳이 A 한개인 경우 ABCDEAEDCBA 로 만들 수 있습니다.

 

따라서 다음을 만족하지 않는 경우에는 모두 불가능으로 처리해주면 됩니다.

 

다음의 경우들을 만족하는 경우에는 펠린드롬을 출력해야 합니다.

펠린드롬은 왼쪽 중간 오른쪽으로 나눌 수 있는데, 왼쪽과 오른쪽은 뒤집으면 같아집니다. 따라서 왼쪽과 중간만 구하면 됩니다.

 

왼쪽을 구하는 방법은 알파벳의 개수가 1개 이상인 알파벳을 찾습니다.

1. 해당 알파벳의 개수가 홀수인 경우

    -> 해당 알파벳이 3개 이상인 경우 2로 나눈 값만큼 왼쪽에 추가해주면 됩니다.

2. 해당 알파벳의 개수가 짝수인 경우 

   -> 해당 알파벳의 개수를 2로 나눈 값만큼 왼쪽에 추가해줍니다.

 

A -> Z로 순서대로 확인하기에 만들어지는 문자열은 항상 사전순으로 앞서게 됩니다.

 

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <string>

using namespace std;

string N;
int cnt;
int alpha[26];
string one, two;
string Left, Mid;

void solve(){
    for(int i = 0; i < 26; i++){
        if(alpha[i] % 2 == 1){
            one += ('A' + i);
            if(alpha[i] / 2 > 0){
                for(int j = 0; j < alpha[i] / 2; j++) Left += ('A' + i);
            }
            Mid += ('A' + i);
        }
        else if(alpha[i] % 2 == 0 && alpha[i] > 0){
            two += ('A' + i);
            for(int j = 0; j < alpha[i] / 2; j++) Left += ('A' + i);
        } 
    }
    if(cnt % 2 == 0 && one.size() > 0) cout << "I'm Sorry Hansoo";
    else if(cnt % 2 == 1 && one.size() > 1) cout << "I'm Sorry Hansoo";
    else{
        cout << Left << Mid;
        reverse(Left.begin(), Left.end());
        cout << Left;
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    cnt = N.size();
    for(int i = 0; i < N.size(); i++){
        alpha[N[i] - 'A']++;
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요