백준 1213 - 파이썬

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

1213번: 팰린드롬 만들기

문제 풀이

처음에 팰린드롬이 뭔지도 몰라 찾아보니 회문이었다. 사실 팰린드롬의 뜻을 알아도 어떻게 풀어야 하나 감도 찾지 못했다. 문제를 고민할 시간도 없고 어떻게 풀어야 할지에 대한 감도 없어 그냥 바로 다른 사람들의 블로그를 참고했다.

 

코드

import sys
from collections import Counter
input = sys.stdin.readline

word = list(map(str,input().strip()))
word.sort()
check = Counter(word)

cnt = 0
center = ""

for i in check:
  if check[i] % 2 != 0:
    cnt += 1
    center += i
    word.remove(i)

  if cnt > 1:
    break

if cnt > 1:
  print("I'm Sorry Hansoo")

else:
  res = ""
  for i in range(0, len(word),2):
    res += word[i]

  print(res + center + res[::-1])

Counter 라는 함수를 이용하여 풀었는데, 이 함수는 각 문자열의 개수를 세어주는 함수이다. 전체적인 알고리즘은 다음과 같다.

 

1. 정답이 여러개인 경우 사전순으로 출력하라는 조건이 문제에 있었으므로, 입력 값들을 사전 순인 오름차순으로 정렬하였다.

2. Counter 함수로 문자열 개수 파악

3. 문자의 개수가 홀수인 문자가 2개 이상인 경우에는 팰린드롬으로 못 바꿈(ex. AABBCDBBAA)

4. 문자의 개수가 홀수인 문자를 제외하고, 남은 문자의 절반을 합쳐준다.

 

보여진 코드는 위 과정을 구현한 것이다. 마지막에 문자열을 반으로 나누는 것이 이해가 안 갈수 있는데, 입력된 문자의 총 개수를 2칸씩 건너뛰며 반복문을 돌아 A가 4개인 경우에는 2번만, B가 2개인 경우에는 한번만 더해지도록 구현한 것이다. 그리고 이를 res[::-1]이라는 코드로 전체를 뒤집어 준 것이다. 이 코드를 다른 방식으로 풀 수 있는데, 해당 방식은 이 블로그에서 참고했다.

for k, v in sorted(check_word.items()):
  result += (k * (v // 2)) # 현재 갯수를 2로 나눠 절반만 더함
print(result + mid + result[::-1])

 

느낀점

이번 문제를 풀면서 counter라는 함수와 슬라이싱 기법을 통해 문자열 전체를 거꾸로 출력하는 방법에 대해서 배웠다. 일주일만에 알고리즘을 풀어서 그런지 감도 좀 떨어진 느낌이 들었다. 간단한 규칙만 찾으면 풀 수 있는 문제였기에 꾸준히 했다면 풀 수 있었을거 같아 아쉽다. 최근에 바빠서 풀지 못했지만 앞으로는 일주일에 최소한 3~4문제는 꾸준히 풀어야 되겠다.