[Baekjoon] 1213번 : 팰린드롬 만들기 (Python, 문자열, 그리디)

[Baekjoon] 1213번 : 팰린드롬 만들기 (Python, 문자열, 그리디)

 

목차

 

 

 

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

1213번: 팰린드롬 만들기

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 84ms / 코드 길이 698B

 

'팰린드롬(palindrome)'은 거꾸로 읽어도 제대로 읽는 것과 같은 것을 의미하며 '회문'이라고도 한다.

https://ko.wikipedia.org/wiki/%ED%9A%8C%EB%AC%B8

회문 - 위키백과, 우리 모두의 백과사전

 

"기러기 토마토 스위스 인도인 별똥별 우영우~ " - 이상한 변호사 우영우(2022)

 

 

알파벳 대문자로만 이루어진 본 문자에 대해 필자는 짝수 알파벳의 수와 홀수 알파벳의 수를 각각 구해 사전순에서 앞서는 것 순으로 조합을 만들었다.

 

 

def palindrome():
    even_tmp = ''
    odd_tmp = ''

    if len(odd):
        odd_tmp += odd[0][0]
        even_tmp += odd[0][0] * ((odd[0][1] - 1)//2)

    for i in range(len(even)):
        even_tmp += even[i][0] * (even[i][1]//2)

    srts = sorted(even_tmp)
    res = ''.join(srts) + odd_tmp + ''.join(srts[::-1])
    print(res)

s = input()

alpha = [0] * 26
for i in s:
    alpha[ord(i)-ord('A')] += 1

odd = []
even = []
for i in range(len(alpha)):
    if alpha[i]:
        if alpha[i] % 2 == 0:
            even.append((chr(i + ord('A')), alpha[i]))
        else:
            odd.append((chr(i + ord('A')), alpha[i]))

if len(odd) > 1:
    print('I\'m Sorry Hansoo')
else:
    palindrome()

 

 

방법 2 - 메모리 30840KB / 시간 68ms / 코드 길이 355B

 

방법 1을 조금 더 직관적으로 풀어 쓴 솔루션이다. 별도의 메모리 사용으로 인한 추가 시간 소모가 줄어든다.

더욱이 애초부터 알파벳 순으로 진행하므로 별도의 정렬이 필요하지 않음을 알 수 있다.

 

s = input()
alpha_n = [0] * 26
for i in s:
    alpha_n[ord(i)-ord('A')] += 1

odd = 0
odd_tmp = ''
strt = ''

for i in range(len(alpha_n)):
    if alpha_n[i] % 2 == 1:
        odd += 1
        odd_tmp += chr(i+ord('A'))
    strt += chr(i+ord('A')) * (alpha_n[i] // 2)

if odd > 1:
    print("I'm Sorry Hansoo")
else:
    print(strt + odd_tmp + strt[::-1])