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

ungnam·2025년 3월 25일

ps 문자열 백준

문제 설명

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

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

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

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

입력

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

출력

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

접근 방법

기존 코드

s = list(input())
s.sort()
i = 0
r = [''] * 50

a = []
for c in s:
  if a and c == a[-1]:
    a.pop()
    r[i] = r[50 - i - 1] = c
    i += 1
  else:
    a.append(c)

if len(a) >= 2:
  print("I'm Sorry Hansoo")
else:
  if a:
    r[i] = a[0]
  print(''.join(r))

🔹 문제점

고정 크기 배열 사용 → r = [''] * 50을 사용하여 메모리를 낭비함.
정렬 (s.sort())을 이용한 접근 → 불필요한 O(N log N) 연산이 발생함.
짝수 개수 문자 처리가 비효율적 → 리스트 a를 활용해 직접 관리하여 코드가 직관적이지 않음.

개선된 방법

🔹 핵심 아이디어

문자 빈도를 먼저 세고, 홀수 개수 문자가 2개 이상이면 불가능하다고 판단한다.
Counter를 활용하여 O(N)으로 문자 개수를 계산하고, 정렬을 최소화하여 효율성을 높인다.
리스트를 활용하여 한 번의 join()으로 문자열을 조합하여 성능을 개선한다.

개선된 코드

from collections import Counter

s = input()
count = Counter(s)  # 각 문자의 개수를 센다.

odd_char = None  # 홀수 개수 문자가 하나 존재할 경우 저장할 변수
half_palindrome = []  # 팰린드롬 절반을 만들 리스트

# 문자를 사전순으로 정렬하여 처리
for char, freq in sorted(count.items()):
    if freq % 2 == 1:  # 홀수 개수 문자 발견 시
        if odd_char:  # 이미 홀수 개수 문자가 존재하면 팰린드롬 불가능
            print("I'm Sorry Hansoo")
            exit()
        odd_char = char  # 홀수 문자를 저장한다.
    half_palindrome.append(char * (freq // 2))  # 짝수 개수 문자 절반 저장

# 결과 조합
first_half = ''.join(half_palindrome)  # 절반 문자열 생성
second_half = first_half[::-1]  # 첫 절반을 뒤집어서 사용

if odd_char:
    result = first_half + odd_char + second_half  # 홀수 문자가 있다면 가운데 삽입
else:
    result = first_half + second_half  # 그대로 붙이기

print(result)

✨ 쉽게 이해하는 코드 설명

문자의 개수를 센다. (Counter 활용)
- 예를 들어 입력이 AAABB라면 { 'A': 3, 'B': 2 }가 된다.
홀수 개수 문자가 2개 이상인지 확인한다.
- A는 3개, B는 2개이므로 A만 홀수 개수이다. → 팰린드롬 가능!
- 만약 ABC처럼 홀수 개수가 2개 이상이면 I'm Sorry Hansoo 출력.
짝수 개수 문자의 절반을 저장한다.
- AAABB에서 A는 3개 → A 하나는 남기고 A 1개를 저장한다.
- B는 2개 → B 1개를 저장한다.
- 결과: half_palindrome = ['A', 'B']
절반을 만들고 뒤집어서 조합한다.
- first_half = "AB"
- second_half = "BA" (뒤집기)
- odd_char = "A" (홀수 개수 문자)
- 결과: "ABABA"