[문자열/백준] 1213번 : 팰린드롬 만들기

- 문제 : https://www.acmicpc.net/problem/1213

 

문제 이해 

- 주어진 영어 단어를 대칭을 이루는 팰린드롬으로 만들 수 있는지 확인하는 문제다.

 

- 만들 수 있다면 사전 순으로 가장 먼저인 문자를 출력하고, 못 만든다면 'I'm Sorry Hansoo'를 출력하면된다.

 

- 어떻게 대칭인 단어를 만들 수 있을까 생각하다가 먼저 단어를 입력 받은 뒤 각 알파벳과 알파벳의 개수를 딕셔너리에 저장한다. 

 

- 딕셔너리를 순차적으로 진행하면서 first와 second 배열에 알파벳들을 append 한다.

(대칭을 이뤄야 하므로 first와 second에 하나의 알파벳을 하나씩 넣어주고 마지막에 합치면 대칭인 단어를 만들 수 있다)

 

- 이때 second는 그냥 순차적으로 first처럼 append를 해주고 마지막에 출력할 때만 뒤집어서 출력하면 된다.

 

- 좀 더 생각해 봐야할 부분은 한 알파벳의 개수가 홀수이거나 팰린드롬을 만들지 못하는 경우이다.

  1. 한 알파벳의 개수가 홀수인 경우는 하나만 나오면 괜찮지만, 알파벳 하나만 따로 저장(middle)한 뒤 마지막에 추가해 주면 된다.

  2. 만약 홀수 개수인 알파벳이 2개 이상이 된다면 그 즉시 팰린드롬을 만들지 못하기 때문에 바로 실패 케이스로 가야한다. 

 

풀이 로직

- 단어를 입력받아 리스트로 바꾼 뒤 정렬한다. (사전순으로 가장 먼저인 단어를 만들어야하기 때문)

 

- 단어의 리스트에 있는 알파벳의 개수를 세기 위해 Counter 라이브러리를 이용한다.

 

- 각 변수들을 초기화하는데, 목적은 다음과 같다.

  first : 왼쪽에 놓을 단어를 추가하는 배열

  second : 오른쪽에 놓을 단어를 추가하는 배열

  flag : 알파벳 개수가 홀수인 게 1개인 것을 확인하는 변수

  check :  팰린드롬 성공/실패 여부를 확인하는 변수

  middle : 홀수 개인 알파벳을 가운데 놓기 위해 따로 저장하는 변수

 

- 주어진 단어 배열을 탐색하면서 각 알파벳의 개수가 홀수인 경우와 짝수인 경우로 나눠서 진행한다.

  1. 홀수인 경우는 이전에 개수가 홀수인 알파벳이 없었는지 확인하고, 중간에 넣을 middle을 갱신한 뒤 flag를 False로 바꾼다. 

     개수도 하나 줄인 뒤 반복문을 통해 왼쪽과 오른쪽에 넣을 알파벳을 하나씩 넣는다.

  2. 만약 알파벳 개수가 홀수인데 이전에 이미 같은 유형의 알파벳이 있었다면 팰린드롬을 만들지 못하므로 반복문을 바로 break한다.

  3. 짝수인 경우에는 별도의 과정없이 반복문을 통해 왼쪽과 오른쪽에 알파벳을 하나씩 넣어주면 된다.

 

- check가 False인 경우는 바로 팰린드롬이 실패한 것이므로 실패 문장을 출력한다. 아니라면 first 끝에 middle을 추가한 뒤 first는 순서대로, second는 역순으로 붙여서 출력한다.

 

정답 풀이 

from collections import Counter

words = list(input())
words.sort()
words_dic = Counter(words)

first, second = [], []
flag = True
check = True
middle = ''
for each in words_dic.keys():
    
    if words_dic[each] % 2 == 1:
        if flag:
            middle = each
            flag = False
            words_dic[each] -= 1
            while words_dic[each] > 0:
                first.append(each)
                second.append(each)
                words_dic[each] -= 2
        else:
            check = False
            break
                
    else:
        while words_dic[each] > 0:
            first.append(each)
            second.append(each)
            words_dic[each] -= 2
            
           
           
if not check:
    print("I'm Sorry Hansoo")
else:
    first.append(middle)
    print(''.join(first) + ''.join(second[-1::-1]))