[백준] 1213번 팰린드롬 만들기 파이썬 풀이

1213번: 팰린드롬 만들기

[문제]

---

[코드]

name = input()
names = [0] * 26

for j in name:
    names[ord(j) - 65] += 1

a = 0
a_a = ""
a_c = ""

for i in range(26):
    if names[i] % 2 == 1:
        a += 1
        a_a += chr(i + 65)
    a_c += chr(i+65) * (names[i] // 2)

if a > 1:
    print("I'm Sorry Hansoo")
else:
    print(a_c + a_a + a_c[::-1])​

---

[해설]

일단 '팰린드롬'이라는 용어에서 막혔다.

문제에서는 팰린드롬에 대한 설명이 자세히 나와있지 않기 때문에

팰린드롬을 처음 접한 사람이라면 어떤식으로 문제를 접근해야할지 막막할 것이다.

 

팰린드롬이란? 

간단하게 설명해서 한 단어를 뒤집었을 때도 같은 문자일 때 팰린드롬이라고 한다. (가장 먼저 떠오른건 우영우... 기러기, 스위스)

 

따라서 문제의 핵심은 주어진 단어를 어떻게 변화시켜 팰린드롬을 만들지 이고 만약만들 수 없는 단어라고 판단되면 만들 수 없다고 

결과값을 출력하는 것이 목적이라고 할 수 있다.

 

또한 팰린드롬의 핵심을 알아봐야 이 문제를 해결 할 수 있다.

팰린드롬은 주어진 단어에서 단어를 구성하고 있는 알파벳이 홀 수 갯수인 단어가 1개를 넘어서는 안된다.

 

ex) AACCCBBB 라는 경우에 홀 수 갯수를 가진 알파벳은 C와 B이다 이렇게 되면 팰린드롬을 만들 수 없다.

 

따라서 문제의 1차 핵심은 주어진 단어의 알파벳 갯수를 파악하여 홀 수 갯수를  판단하는 것이다.

여기서 사용되는 것이 ord와 dp인 names이다

 

name = input()
names = [0] * 26

for j in name:
    names[ord(j) - 65] += 1

name이라는 변수를 통해서 먼저 단어를 받는다

그리고 알파벳 갯수 만큼 dp를 만들어주며 이를 names라는 변수로 받는다

 

그리고 주어진  단어를 for 문으로 돌면서 해당 알파벳의 갯수를 names에 저장한다

Ex) 'ABBAA'인 경우

names는 [3, 2, 0, 0, 0, 0 ....]이 되며 이때 사용하년 ord()는 알파벳을 숫자로 변환 해주고 여기서 65를 뺀 이유는 'A'가 65이기 때문이다.

[python] 파이썬 ord 함수, chr 함수 설명과 예제

 

이제 단어가 갖고 있는 알파벳 갯수 정보를 갖게 되었다.

다음으로 필요한 단계가 홀 수 갯수를 판단하고 가능하다면 팰린드롬 단어를 만들어 출력하는 것이다.

a = 0
a_a = ""
a_c = ""

for i in range(26):
    if names[i] % 2 == 1:
        a += 1
        a_a += chr(i + 65)
    a_c += chr(i+65) * (names[i] // 2)

if a > 1:
    print("I'm Sorry Hansoo")
else:
    print(a_c + a_a + a_c[::-1])​

a = (홀 수 갯수를 저장하는 변수)

a_a = 홀 수 갯수의 알파벳 하나를 저장하는 변수 (홀 수가 1개라면 팰린드롬이 가능하며 이 알파벳 하나를 단어 중앙에 두어야하기 때문에)

a_c = names에 존재하는 모든 알파벳을 갯수의 절반 만큼 저장하는 문자열 (절반만큼 저장하는 이유는 출력때 반반 나눠서 앞과 끝에 추가해주어야하는데 따라서 2번사용하기 때문에 절만반 있으면 된다)

 

이제 26만큼 for문을 돌면서(알파벳 숫자 및 names의 len) 각 알파벳의 수를 파악한다. 

만약 알파벳의 보유가 홀수라면 (if names[i] % 2 == 1) - a에 +=1를 해주고 그 알파벳 하나를 저장한다.

그리고 for문마다 보유한 알파벳 수의 절반을 a_c에 저장해준다.

 

만약 a>1 크다면 즉, 홀 수 갯수의 알파벳이 2개이상이라면 우리는 팰린드롬을 만들 수 없다

따라서 문제에서 요구하는 문장을 출력해주고

아닐 경우 우리는 팰린드롬을 출력해야한다

 

팰린드롬을 만드는 방법은 아래와 같다 

a_c [이는 기존 단어가 보유한 알파벳 수를 절반씩 갖고 있는 문자열 = 항상 사전순으로 갖고 있다, 왜냐하면 a부터 for문이 돌아 추가되었기 때문이다] + a_a [ 홀 수 갯수인 알파벳 하나 = 이 친구는 가운데에 위치해야한다] + a_c의 역순서 [뒤집었을 때 같아야하기 때문에 a_c를 뒤집어서 추가해준다]

 

➡️ 쉽게 표현하면 a_c + a_a + 역a_c로 출력해주면 된다.

 

 

 

🚩문제 핵심 요약

 1. ord 와 for문을 활용하여 단어를 구성하고 있는 알파벳 갯수 파악

 2. for 문과 if문을 활용한 홀 수 갯수 파악

 3. 이를 통해 팰린드롬을 출력하는 방법 파악