[백준 | 파이썬] 1213 : 팰린드롬 만들기

💡 규칙만 잘 정리하면 쉽게 풀리는 문제

문제

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

입력

첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

풀이 방법

• 사전순으로 앞서는 것을 출력하기 때문에, 입력을 받은 뒤 알파벳 순으로 정렬한다.
• 입력에 포함된 알파벳별 갯수를 계산한다.
• 팰린드롬은 반으로 접었을 때 정확히 일치하는 문자열의 형태이다. 따라서 가운데를 기준으로 앞부분만 만들면 뒷부분은 앞부분을 뒤집어서 만들 수 있다.
  • 단, 홀수 알파벳이 2개 이상 포함되어있으면 만들 수 없다.
    • ex) AAAABBBC
• 중복 문자열을 제거한 뒤 A부터 시작한다.
  • 홀수알파벳이 1개인 경우, A부터 시작해서 알파벳 개수를 2로 나눈 몫만큼 알파벳을 문자열에 추가한다. 알파벳을 모두 추가했으면 문자열을 반전시켜서 뒷부분을 만들어 붙인다.
    • 이때 홀수 알파벳을 사이에 넣어 준다.
  • 홀수알파벳이 하나도 없을 경우, A부터 시작해서 알파벳 개수를 2로 나눈 몫 만큼 알파벳을 문자열에 추가한다. 알파벳을 모두 추가했으면 문자열을 반전시켜서 뒷부분을 만들어 붙인다.

코드

s = list(input())
alphabet = [chr(i) for i in range(65, 91)]
alphabet_cnt = [0 for i in range(len(alphabet))]

odd_cnt = 0
odd_chr = ""
for i in range(len(alphabet)):
    alphabet_cnt[i] = s.count(alphabet[i])
    if alphabet_cnt[i] % 2 == 1:
        odd_cnt += 1
        odd_chr = alphabet[i]

s = sorted(list(set(s)))
ans_front = []
for j in s:
    if odd_cnt >= 2:
        print("I'm Sorry Hansoo")
        quit()
    ans_front.append(j*(alphabet_cnt[alphabet.index(j)] // 2))

ans_back = list(reversed(ans_front))

if odd_cnt == 1:
    ans_front.append(odd_chr)
ans = ans_front + ans_back

print(*ans, sep="")

코드 2

조금 다른 방법!

알파벳으로 구성된 문자열을 따로 만들지 않고, 해당 알파벳을 나타내는 기호로 인덱스를 사용(A = 0 = 65)했다.

대문자 A를 아스키코드로 바꾸면 65임을 이용했다.

불필요한 연산을 좀 더 줄일 수 있는 방법인것 같다.

alphabet_cnt = [0]*26 # 알파벳 갯수를 담는 배열

S = input()
for i in S:
    alphabet_cnt[ord(i)-65] += 1

odd_cnt = 0
odd_idx = 0
for j in range(26):
    if alphabet_cnt[j] % 2 == 1:
        odd_cnt += 1
        odd_idx = j

if odd_cnt > 1:
    print("I'm Sorry Hansoo")
    quit()

ans_front = ""
for k in range(26):
    ans_front += chr(k+65)*(alphabet_cnt[k]//2)
ans_back = ans_front[::-1]

if odd_cnt == 1:
    ans_front += chr(odd_idx+65)

print(ans_front+ans_back)