[백준/Python] 1213 : 펠린드롬 만들기

 

 

 

우선 palindrome을 만드는 조건들을 생각해보자.

 

1. 짝수 길이의 문자열

- 문자열이 짝수 길이일 경우, 각 문자는 짝을 이루어야 함

ex) aabb , ccddcc , 1221 과 같이 각각의 문자가 동일한 수만큼 있어야 함

 

2. 홀수 길이의 문자열

- 문자열이 홀수 길이일 경우, 모든 문자는 짝을 이루어야 하지만 중앙에 위치한 '한 문자'만 짝이 없어도 됨

ex) aba , abcba , racecar 과 같이 중앙에 있는 문자를 제외하고는 나머지 문자들은 짝을 이뤄야 함

 

즉, palindrome을 만들기 위해서는...

- 짝수 길이의 문자열 : 모든 문자가 짝수 번 등장해야 함

- 홀수 길이의 문자열 : 하나의 문자만 홀수 번 등장할 수 있으며, 나머지 문자는 모두 짝수 번 등장해야 함

 

위 아이디어를 기반으로 코드를 작성해보면 다음과 같다.

 

<전체 코드>

def frequency(s):
    freq = {} # 딕셔너리 {a:2. b:2, c:1}
    for char in s:
        if char in freq:
            freq[char] +=1
        else : freq[char] = 1
    return freq

def palindrome(word):
    freq = frequency(word) # 빈도수 세기
    
    odd = 0 # 홀수 번 등장하는 문자 개수 (1개까지만 palindrome 생성 가능)
    for cnt in freq.values():
        if cnt % 2 != 0:
            odd += 1
    if odd > 1:
        print("I'm Sorry Hansoo")
        return
    
    left = []
    mid = ''
    right = []
    
    for char in sorted(freq.keys()):
        cnt = freq[char]
        half = cnt // 2
        left.append(char*half)
        right.append(char*half)
        if cnt % 2 != 0 : # 빈도가 홀수인 경우
            mid = char 
    
    palindrome = ''.join(left) + mid + ''.join(right[::-1])
    print(palindrome) # abcba


word = input() # aabbc
palindrome(word)

 

코드를 작성하기 쉽게 우선 간단한 예시 문자열을 가정하였음 >> aabbc

이를 input으로 입력받고, palindrome 생성 가능 여부를 판단하고 생성해주는 함수 palindrome() 과 입력받은 문자열의 문자별 빈도수를 세어주는 frequency() 함수 두 개를 생성하였다.

 

사실 찾아보니까 import collections from Counter로 Counter를 불러와서 빈도수를 자동으로 측정해주는 것이 있다고는 하는데, 일단 사용하지 않고 하드코딩으로 딕셔너리를 사용하여 {문자 : 빈도수} 구조로 생성하도록 작성함

 

def frequency(s):
    freq = {} # 딕셔너리 {a:2. b:2, c:1}
    for char in s:
        if char in freq:
            freq[char] +=1
        else : freq[char] = 1
    return freq

def palindrome(word):
    freq = frequency(word) # 빈도수 세기
    
    odd = 0 # 홀수 번 등장하는 문자 개수 (1개까지만 palindrome 생성 가능)
    for cnt in freq.values():
        if cnt % 2 != 0:
            odd += 1
    if odd > 1:
        print("I'm Sorry Hansoo")
        return

 

이후 문자열에서 홀수 번 등장하는 문자(빈도수가 홀수인 문자)의 경우에는 문자열 내에서 1종류까지만 palindrome을 형성할 수 있기 때문에 이를 판별하기 위한 odd 변수를 생성하여 딕셔너리의 values 들을 모두 순회하며 빈도수가 홀수인 문자 종류를 구해준다.

 

만약 odd가 2이상이면 빈도수가 홀수인 문자가 2종류 이상이라는 의미이므로 palindrome을 형성할 수 없다.

이 경우 I'm Sorry Hansoo를 출력하고 프로그램을 종료!

 

여기까지 무사히 통과한 문자열은 이제 모든 문자 종류가 짝수 번 등장하거나, 홀수 번 등장하는 문자 종류가 1개밖에 없는 문자열인 것을 전제로 한다.

 

    left = []
    mid = ''
    right = []
    
    for char in sorted(freq.keys()):
        cnt = freq[char]
        half = cnt // 2
        left.append(char*half)
        right.append(char*half)
        if cnt % 2 != 0 : # 빈도가 홀수인 경우
            mid = char 
    
    palindrome = ''.join(left) + mid + ''.join(right[::-1])
    print(palindrome) # abcba

 

palindrome 문자열을 구분하자면 왼쪽/중간/오른쪽 이렇게 구분할 수 있고, 이를 기반으로 palindrome을 생성하기 위해 각각 left = [], mid = ' ' , right = [] 를 만들어주었음

이렇게 세팅을 완료했으면 이제 freq 딕셔너리를 순회하면서 문자의 빈도수 별로 2로 나눈뒤 각각 왼쪽과 오른쪽 리스트에 동등하게 넣어주면 된다~

 

여기서 내가 한 번 틀렸던 부분이 ' 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다'라는 조건을 놓친 것이었는데, 이를 맞게 하기 위해 기존에 for char, cnt in freq.items() 로 작성했던 것을 for char in sorted(freq.keys())로 수정하여 문자를 사전순으로 정렬한 뒤에 빈도수를 적용하는 작업을 진행하였다.

그리고 중심 부분인 mid에는 빈도가 홀수인 문자만 들어가면 되므로 mid = char로 넣어준다.

 

각각 left, mid, right에 문자들을 잘 쌓았다면 이제 이를 합치면 되는데, 추론 가능하다시피 right 부분은 left와 현재 똑같은 순서로 쌓여있으므로 palindrome을 만들기 위해선 이를 역순으로 바꿔줘야 하기 때문에 right [::-1]로 작성해주고 join 시켜주었다. (reversed(right) 로도 가능)

 

이렇게 작성하면 palindrome을 정상적으로 변환하여 출력할 수 있게 된다!