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

0. 문제

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

 

주어진 알파벳 대문자로 구성된 문자열을 재배열하여 팰린드롬을 만들어내는 문제입니다. 참고로 팰린드롬이란, 거꾸로 읽어도 같은 (대칭되는) 문자열을 말합니다.

---

1. 문제풀이 핵심

a) 알파벳 개수 카운팅

• 주어진 문자열에서 각 알파벳의 개수를 카운트합니다.
• 팰린드롬을 만들기 위해서는 문자열의 길이가 홀수일 때, 홀수인 알파벳이 정확히 1개여야 하고, 길이가 짝수일 때는 홀수인 알파벳이 없어야 합니다.

b) vector를 스택처럼 활용

• 팰린드롬을 만들기 위해 알파벳을 양쪽에 대칭으로 배치해야 합니다.
• 이를 위해 vector를 스택처럼 사용하여 알파벳을 반으로 나누어 저장하고, 다시 역순으로 출력합니다.

c) 홀수인 알파벳을 중간에 배치

• 문자열의 길이가 홀수인 경우, 홀수 개의 알파벳을 팰린드롬의 중앙에 위치시켜야 합니다.
• 먼저 알파벳을 반으로 나눈 뒤, 홀수 알파벳을 출력하고 나머지 반쪽을 출력하는 방식으로 팰린드롬을 만듭니다.

d) 사전순으로 가장 앞에 오는 조합 출력

• map을 사용하여 알파벳의 개수를 카운팅하기 때문에, map의 특성상 키가 자동으로 정렬됩니다.
• 따라서 알파벳을 사전순으로 정렬할 필요가 없이 map을 순회하는 것만으로도 사전순으로 정렬된 결과를 얻을 수 있습니다.

 

---

2. 문제풀이에 사용된 개념

 

map을 이용한 알파벳 개수 카운팅

 

• map을 사용하여 문자열의 각 알파벳이 몇 번 등장하는지 카운트합니다.
• 키는 알파벳, 값은 그 알파벳의 개수입니다.

 

 

팰린드롬의 특징을 활용한 조건 체크

문자열의 길이에 따라 홀수 개의 알파벳이 몇 개 있어야 하는지 체크합니다.

 

 

vector를 스택처럼 사용하기

팰린드롬을 만들기 위해 문자열의 반만 저장하며 출력하고, 이를 다시 꺼내며 출력합니다.

 

 

---

 

3. 문제풀이 코드

#include<bits/stdc++.h>

using namespace std;

string s; // 임한수의 영어 이름. 알파벳 대문자로만
map<char, int> m; // 각 알파벳의 개수를 저장
char hol; // 홀수인 알파벳
vector<char> res; // 결과를 저장할 벡터

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    int nameLen = s.size(); 

    // 각 알파벳의 개수를 카운트하여 map에 저장
    for(int i = 0; i < nameLen; i++){
        char cur = s[i];
        auto it = m.find(cur);
        if(it != m.end()){
            it->second++;
        } else {
            m.insert({cur, 1});
        }
    }

    int num = 0; // 홀수인 알파벳 개수

    // 홀수인 알파벳의 개수 찾기
    for(auto i : m){
        if(i.second % 2 != 0) {
            num++;
            hol = i.first; // 홀수인 알파벳을 저장
        }
    }

    // 홀수 개수 알파벳이 1개 이상일 때와 짝수일 때의 조건 체크
    if(nameLen % 2 != 0 && num != 1 || nameLen % 2 == 0 && num != 0 ){ 
        cout << "I'm Sorry Hansoo";
        return 0;
    }

    // 각 알파벳의 절반을 벡터에 저장하여 대칭으로 출력 준비
    for(auto i : m){
        for(int j = 0; j < i.second / 2; j++){
            res.push_back(i.first);
            cout << i.first;
        }
    }

    // 홀수인 알파벳이 있으면 중간에 출력
    if(num) cout << hol;

    // 벡터에서 pop하여 대칭으로 출력
    int resSize = res.size();
    for(int j = 0; j < resSize; j++){
        cout << res.back();
        res.pop_back();
    }
}

 

 

3-1. 코드 로직 설명

1. 알파벳 개수 카운트
   • 입력받은 문자열에서 각 알파벳의 개수를 map에 저장합니다.
2. 홀수인 알파벳 체크
   • 문자열의 길이가 홀수인 경우에는 홀수 개의 알파벳이 정확히 1개여야 합니다.
   • 길이가 짝수인 경우에는 모든 알파벳의 개수가 짝수여야 합니다.
   • 이러한 조건이 만족되지 않으면 팰린드롬을 만들 수 없으므로 "I'm Sorry Hansoo"를 출력합니다.
3. 팰린드롬 만들기
   • 알파벳의 절반을 vector에 저장하면서 출력합니다.
   • 홀수인 알파벳이 있는 경우에는 중간에 출력합니다.
   • vector의 back()과 pop_back()을 사용하여 남은 절반을 꺼내며 역순으로 출력합니다.

 

---

 

4. 문제풀이에 사용된 함수

map.find(key)

 

• key가 map에 존재하는지 확인하고, 있으면 해당 요소의 이터레이터를 반환합니다.
• 존재하지 않으면 map.end()를 반환합니다.

 

 

vector의 back() ,  pop_back()

 

• back()은 vector의 마지막 요소를 참조합니다.
• pop_back()은 vector의 마지막 요소를 제거합니다.

** 핵심 = vector를 스택처럼 사용하여 LIFO(Last In, First Out) 구조를 구현할 수 있습니다.

 

---

 

5. 요약 정리

 

• 팰린드롬의 조건: 문자열의 길이에 따라 홀수 개의 알파벳이 있을 수 있는지 여부를 판단하고, 이에 따라 팰린드롬을 생성할 수 있는지를 확인합니다.
• map의 활용: 각 알파벳의 개수를 카운팅하는 데 map을 사용하여 자동 정렬(사전순)과 빠른 검색을 활용했습니다.
• 팰린드롬 생성: vector를 사용하여 반으로 나눈 문자열을 저장하고, 이를 역순으로 출력하여 팰린드롬을 생성합니다.
• 중요 포인트:
  • 대칭을 만들기 위해서는 이름의 길이(짝수,홀수)에 따라 홀수인 알파벳이 0개 또는 1개만 있어야 합니다.
  • map을 통해 알파벳 개수를 관리하면서 자동으로 사전순으로 정렬된 결과를 얻을 수 있습니다.