[그리디] 코딩테스트 문제 TIL (팰린드롬 만들기) - 백준 1213번

말하는 감자·2024년 12월 26일

TIL algorithm baekjoon greedy python 구현 그리기 백준 파이썬

코딩테스트 유형별 풀이

목록 보기

52/67

1. 오늘의 학습 키워드

구현
그리디

2. 문제: 1213. 팰린드롬 만들기

단계: 🥈 실버 3단계
주제:
출처: https://www.acmicpc.net/problem/1213

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

AABB

예제 출력 1 복사

ABBA

예제 입력 2 복사

AAABB

예제 출력 2 복사

ABABA

예제 입력 3 복사

ABACABA

예제 출력 3 복사

AABCBAA

예제 입력 4 복사

ABCD

예제 출력 4 복사

I'm Sorry Hansoo

3. 문제 풀이

Step1. 문제 이해하기

이 문제는 문자열을 적절히 재배열하여 팰린드롬을 만드는 문제입니다. 팰린드롬은 앞뒤가 같은 문자열로, 주어진 조건에서 이를 만족하는지 확인하고, 가능한 경우 사전순으로 가장 앞서는 팰린드롬을 출력해야 합니다.

불가능한 경우 "I'm Sorry Hansoo”을 출력합니다.

Step2. 문제 분석하기

우선, 팰린드롬의 성질을 알아야 합니다.

주어진 문자열이 팰린드롬이 될려면 문자열을 구성하는 각 문자들의 빈도를 파악해야 합니다.

문자 개수가 짝수인 경우: 모든 문자는 짝수 개씩 있어야 함.
문자 개수가 홀수인 경우:
- 단 하나의 문자만 홀수 개로 나타날 수 있음 (가운데에 위치).
- 나머지 문자는 모두 짝수 개여야 함.

그래서 주어진 문자열의 빈도를 파악하고, 홀수 개수 문자가 몇 개인지를 파악해야 합니다. 만약 2개 이상인 경우 주어진 문자열은 팰린드롬이 될 수 없습니다.

이를 바탕으로 코드 설계를 해보도록 하겠습니다.

Step3. 코드 설계

문자 빈도 수 계산:
- 주어진 문자열에서 각 알파벳의 빈도를 계산합니다.
홀수 개수 확인:
- 홀수 개수 문자가 2개 이상이면 팰린드롬 생성 불가능 → "I'm Sorry Hansoo" 출력. → 홀수 개수를 측정하는 변수가 필요함!
팰린드롬 구성:
- 홀수 개 문자는 팰린드롬의 중앙에 위치.
- 나머지 문자들은 짝수 개로 나뉘어 반씩 앞뒤에 배치.
- 사전순 출력을 위해 알파벳 순으로 정렬하여 처리.
결과 출력:
- 구성된 팰린드롬 문자열을 출력.

Step4. 코드 구현

from collections import Counter
import sys
name = sys.stdin.readline().strip()
def sol(name):
    odd_char = 'None'
    odd_cnt = 0
    counter = Counter(name)
    left = []
    for char in sorted(counter.keys()):
        count = counter[char]
        if count % 2 == 1: # 홀수
            odd_cnt += 1
            odd_char = char
            if odd_cnt > 1:
                return "I'm Sorry Hansoo"
        left.append(char * (count // 2))
    
    left = ''.join(left)
    center = odd_char if odd_cnt == 1 else ""
    right = left[::-1]
    return ''.join([left, center, right])
print(sol(name=name))

코드 설명:
- 문자 빈도 수 계산:
  - Counter(name)를 통해 주어진 문자열의 각 문자 빈도를 계산합니다.
  - 결과는 각 문자의 등장 횟수를 담은 딕셔너리 형태입니다.
- 홀수 개수 확인:
  - count % 2 == 1 조건으로 홀수 빈도의 문자를 확인합니다.
  - 홀수 문자가 2개 이상이면 팰린드롬을 만들 수 없으므로 "I'm Sorry Hansoo"를 반환합니다.
- 팰린드롬 구성:
  - 각 문자를 정렬(sorted(counter.keys()))하여 사전순으로 처리합니다.
  - 문자 빈도의 절반(count // 2)만큼 left 리스트에 추가합니다.
  - 홀수 개 문자는 odd_char로 저장하고, 팰린드롬의 중심(center)에 위치합니다.
  - left는 팰린드롬의 왼쪽 절반이며, 이를 뒤집은 것이 오른쪽(right) 절반입니다.
- 결과 출력:
  - left + center + right 형태로 최종 팰린드롬을 반환합니다.
  - 불가능한 경우에는 "I'm Sorry Hansoo"를 반환합니다.
시간 복잡도: $O(n)$
결과:

4. 마무리

이번 문제는 팰린드롬의 특성을 이해하고 문자열의 빈도를 처리하는 구현 및 정렬의 기초를 활용하는 문제입니다. 그리디 알고리즘의 기본 원칙(가장 사전순으로 구성)과 구현의 조합을 통해 해결했습니다. 문제를 해결하며 문자열 처리와 사전순 정렬의 중요성을 다시 한번 확인할 수 있었습니다. 😊

글 읽어주셔서 감사합니다.