백준 1213 문제 분석 python

mauz·2022년 5월 1일

🐒 팰린드롬 만들기

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

✍ 나의 풀이

import sys

input = sys.stdin.readline


string = input().rstrip()

dic = dict()
for i in string:
    if not i in dic:
        dic[i] = 1
    else:
        dic[i] += 1

center = ''
for key, value in dic.items():
    if value % 2 == 1: # 문자 갯수가 홀수이면
        if len(center) == 0:
            center = key
        else:
            print("I'm Sorry Hansoo")
            break
else: # for-else문
    part = ''
    for key, value in sorted(dic.items()):
        part += key*(value//2)
    
    print(part + center + part[::-1])

어떻게 풀어야할지 몰라서 구글링을 하였다.
짧은 문제이지만 참고한 코드에서 많은걸 얻을 수 있었다.

🧠 문제 이해

풀이에 앞서서 팰린드롬은 우리말로 '회문'을 뜻하고
eye,요기요 처럼 앞으로 읽으나 뒤로 읽으나 같은 문자열을 예로 들 수 있다.

나도 입력된 문자열을 확인해서 딕셔너리에 문자의 갯수를 세는 방법을 생각했지만 그 다음에 홀수문자열과 짝수문자열, 홀수개의 문자와 짝수개의 문자 속에서 규칙을 찾으려 했으나 감을 잡지못하고 다른사람의 코드를 살펴보았다.

참고한 블로그는 https://my-coding-notes.tistory.com/530 이다.

규칙성

블로그의 글쓴이는 홀수개의 문자종류가 두개 이상이면, 회문이 발생하지 못하는 규칙를 찾아내었다.

가령

입력
AAAB
AAABCCC
BBBTTTTT

일때 처럼 말이다.

따라서 다음과 같은 코드가 작성되었다.

center = ''
for key, value in dic.items():
    if value % 2 == 1: # 문자 갯수가 홀수이면
        if len(center) == 0:
            center = key	# 팰린드롬의 가운데 문자로 넣기
        else:	# 문자 갯수가 홀수인게 두 종류 이상이면 실패
            print("I'm Sorry Hansoo")
            break
else: # for-else문
   ...

참고로 이 코드에서는 for-else문이 사용되었다.
for-else문은 for문 내에서 break이 발생하지 않을때 else문이 실행된다. for-else문 설명 블로그

회문 출력하기

문제에서 "정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다" 고 명시되어 있다.

딕셔너리는 순서가 없는 자료구조인데 정렬한뒤 순서대로 출력을 요구하고있다. 어떻하면 좋을까?

sorted(dic.items()) 를 해주면 dic 딕셔너리의 key값을 기준으로 오름차순 정렬을 하여 (key,value) 형태의 튜플을 리스트에 순서대로 담아준다.
딕셔너리 정렬 설명 블로그

딕셔너리가 아닌 리스트는 순서가 있는 iterable 이기 때문에 순서대로 출력할 수 있다!

그리고 회문의 특성은 앞으로 읽으나 뒤로 읽으나 같다는 것이다.
따라서 회문의 절반만큼만 구한뒤, 뒷부분은 앞부분을 뒤집어 주면 된다.

만약 입력이 AAAABB 라면 정답은 AABBAA이고, AAB + BAA로 나타낼수있다. 우리는 AAB만 구하면 되기에
part += key*(value//2) 로 구할 수 있다.

입력이 AAAABBC라면 가운데 문자는 홀수 갯수인 C가 들어간다.
정답은 AABCBAA 이고 AAB + C + BAA 로 나타낼 수 있다.

else: # for-else문
    part = '' # 출력할 문장 앞부분
    for key, value in sorted(dic.items()):
        part += key*(value//2)
    
    print(part + center + part[::-1]) 
     # 앞부분 + 가운데 + 뒷부분