백준 1213 & 팰린드롬 알고리즘(Palindrome Algorithm)

Palindrome

거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열

ex) 기러기, 요기요

 

def is_palindrome(word):
    list_word = list(word)
    for i in range(0, len(list_word) // 2):

        if list_word[i] == list_word[len(list_word) - 1 - i]:
            continue
        else:
            return False

    return True

slice를 이용하여 문자열을 반대로 뒤집은다음에 비교를 하는것도 매우 좋은 방법이다.

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

1213번: 팰린드롬 만들기

처음에는 팰린드롬의 정의를 이용하여 함수를 만들고 입력받은 문자열의 표현가능한 순서들을 순열로 뽑아내 판단하였다

 

def ispalindrome(data):
    data_reverse = data[::-1]
    if data == data_reverse:
        return 1
    else:
        return 0

data = input()
res = []
from itertools import permutations
for i in permutations(data,int(len(data))):
    temp = ''
    if ispalindrome(i):
        for j in range(int(len(data))):
            temp += i[j]
        res.append(temp)
if len(res) == 0:
    print("I'm Sorry Hansoo")
else:
    print(min(res))

하지만 시간초과가 나면서 다른 방법을 생각해야 했다.

 

좀 더 그리디 알고리즘적으로 접근을 해보면 각 알파벳은 짝수가 되어야 팰린드롬이 될 수 있으며

만약 홀수 알파벳이 1개는 괜찮지만 2개이상이 되면 그 문자열은 팰린드롬이 될 수 없다..

import sys
from collections import Counter

word = list(map(str, sys.stdin.readline().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])

Collections 모듈의 Counter 클래스를 활용하여 쉽게 홀/짝수 알파벳을 구할 수 있다.

from collections import Counter
check = Counter(word)

Counter({'B': 4, 'A': 3, 'S': 2, 'D': 1})

마지막 출력은 팰린드롬 형태의 문자열을 출력해야 하기 때문에  짝수만 저장되어있는 list에서 2칸 간격으로 저장 한것을 

원본 + 중간 + 원본_reverse 형태로 출력을 하면 팰린드롬 형태로 만들어진다.