[파이썬] 백준 1213: 팰린드롬 만들기 (실버3)

[파이썬] 백준 1213: 팰린드롬 만들기 (실버3)

 

1213번: 팰린드롬 만들기

---

문제

---

풀이

0. 방향성 생각

입력 예시를 보면 문자열이 짝수일 때, 홀수일 때 다르게 나오는 것을 알 수 있다.

홀수일 때 문자열의 중심점이 필요하고 전체 문자에서 홀수인 알파벳은 하나만 나와야한다.

짝수일 때 문자열의 중심이 없고 모든 알파벳이 짝수번 나와야 한다.

이 조건에 맞지 않으면 I'm Sorry Hansoo를 출력하면 된다.

 

 

1. 입력 받기, 테이블 작성

name = input()
table = {}
length = len(name)
for i in name :
    if i not in table :
        table[i] = 1
    else :
        table[i] += 1

even = [key for key,value in table.items() if value%2 == 0]
odd = [key for key,value in table.items() if value%2 == 1]
even.sort()
odd.sort()

이름을 받은 후에 for문을 돌려서 각 알파벳이 몇번 나왔는지 세준다

이 후 홀수번 나온 알파벳, 짝수번 나온 알파벳을 구분하고 이를 정렬해서 팰린드롬 사용 시 바로 사용할 수 있게 해준다.

 

2. 구현, 출력

if len(name)%2==0: # 짝수문자열 : 모두 짝수
    if len(odd) > 0 :
        print("I'm Sorry Hansoo")
    else :
        answer = ''
        for i in even:
            answer += i*(table[i]//2)
        temp = answer[::-1]
        answer += temp
        print(answer)
        
else :
    if len(odd) != 1 : # 홀수 문자열 : 하나만 홀수
        print("I'm Sorry Hansoo")
        
    else :
        answer = ''
        table[odd[0]] += -1
        
        new_list = even+odd
        new_list.sort()
        for i in new_list:
            answer += i*(table[i]//2)
        answer += odd[0]
        
        temp = answer[:-1] # 대칭점 이전까지
        answer += temp[::-1] # 뒤집어서 더해주고
        print(answer)

먼저 짝수일 때를 확인하면 모든 문자열이 짝수번 등장했어야  하므로 odd = [], 빈 리스트여야 한다.

빈 리스트가 아닐 때에는 실패 문구를 띄워주고 빈 리스트일 경우 정렬된 even을 돌면서 answer에 절반만 추가해준다.

절반만 추가한 후 문자열을 뒤집어서 다시 더해주면 팰린드롬이 완성된다.

 

홀수일 때는 홀수 문자열이 2개 이상 등장하면 대칭을 이룰 수 없으므로 odd 길이가 1이어야 한다.

먼저 odd에 있는 원소가 1번 넘게 등장할 수 있으므로 -1을 먼저 해준 후 대칭점을 빼고도 남은 짝수가가 팰린드롬에 구성될 수 있게 한다.

odd가 1번 넘게 등장한 경우 for문을 돌며 팰린드롬에 구성될 수 있게 새로운 리스트를 만들고 정렬해준다.

이후 짝수일 때와 똑같이 해준 후 맨 뒤에 대칭점 문자를 추가해준다.

그 후 대칭점 이전까지 문자를 얻고 더해준다.

 

---

전체 코드

name = input()
table = {}
length = len(name)
for i in name :
    if i not in table :
        table[i] = 1
    else :
        table[i] += 1

even = [key for key,value in table.items() if value%2 == 0]
odd = [key for key,value in table.items() if value%2 == 1]
even.sort()
odd.sort()

if len(name)%2==0: # 짝수문자열 : 모두 짝수
    if len(odd) > 0 :
        print("I'm Sorry Hansoo")
    else :
        answer = ''
        for i in even:
            answer += i*(table[i]//2)
        temp = answer[::-1]
        answer += temp
        print(answer)
        
else :
    if len(odd) != 1 : # 홀수 문자열 : 하나만 홀수
        print("I'm Sorry Hansoo")
        
    else :
        answer = ''
        table[odd[0]] += -1
        
        new_list = even+odd
        new_list.sort()
        for i in new_list:
            answer += i*(table[i]//2)
        answer += odd[0]
        
        temp = answer[:-1] # 대칭점 이전까지
        answer += temp[::-1] # 뒤집어서 더해주고
        print(answer)

그리디라고 하기에는 정렬조건만 맞추면 돼서 구현에 더 가까운듯

조금 복잡하게 푼거같은데 문제 자체가 어렵진 않아서 괜찮다.