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

💡문제접근

• from itertools import permutations을 이용해서 작성했는데 역시 메모리초과가 발생했다. 입력으로 주어지는 문자열의 최대 길이는 50으로 순열로 가능한 경우의 수를 전부 나타낸다면 엄청난 메모리가 소요되어 메모리초과가 발생하는 것으로 보여진다.
• 이 문제를 풀면서 한 가지 자주 쓰이는 모듈을 발견했는데 바로 Counter모듈이다.
• Counter모듈은 from collections import Counter을 이용해서 사용할 수 있다.
• 이 문제의 테스트케이스 및 다른 케이스들을 비교해서 한 가지 규칙을 알아낼 수 있었다. 만약 홀수 번의 빈도가 나타나는 문자가 2개 이상이라면 팰린드롬 문자를 만들 수 없다.
• 사전 순으로 가장 앞선 팰린드롬 문자열을 출력해야하므로 sorted를 이용해서 오름차순 정렬해서 맨 앞에 있는 팰린드롬 문자열을 출력할 수 있도록 했다.

💡코드(메모리 : 34096KB, 시간 : 68ms)

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

name = input().strip()
check = Counter(name)
cnt = 0
mid = ""
result = ""
for i, j in check.items():
    if j % 2 != 0:
        cnt += 1
        mid = i
        # 만약 홀수 번의 빈도가 나타나는 문자가 2개 이상이라면?
        if cnt >= 2:
            print("I'm Sorry Hansoo")
            sys.exit()

for i, j in sorted(check.items()):
    result += (i * (j // 2))
print(result + mid + result[::-1])

📌 from collections import Counter

• Counter 클래스는 데이터의 갯수를 빠르고 편리하게 셀 수 있도록 지원하는 도구이다.
• 아래 사진은 테스트케이스 중 AAABB를 입력한 결과이다. 이를 토대로 살펴보자.

• collections를 import하여 Counter 클래스를 사용하게 된다면 입력한 문자의 빈도를 딕셔너리(dictionary) 형태로 반환해주는 것을 알 수 있다.

💡소요시간 : 20m