11. 백준 코딩테스트 1213번 문제 python

1213번 문제는 Greedy Algorithm(그리디) 문제 중 하나로, 정답 비율은 36.24% 정도 된다.

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

1213번: 팰린드롬 만들기

 

들어가기 전.

 

그리디(Greedy) 알고리즘은 최적의 해를 구하기 위해 사용되는 알고리즘 중 하나로, 여러 가지 경우 중 하나를 선택해야 할 상황이 올 때 그 순간에 최적인 것만 선택해 나가는 방식을 진행하여 최종적인 해답에 도달하는 알고리즘이다.

 

팰린드롬은 회문 이라고도 하며, 거꾸로읽어도 제대로 읽는 것과 같은 문장이나 단어를 말한다. 우리나라에서 토마토, 기러기 같은 단어나 문장으로는 '수박이 박수' 나 '다시 합창합시다'가 있다.

 

해결방법.

 

문제조차 커플(...)

그리디 알고리즘에 관련된 문제이지만, 나는 그리디알고리즘에 신경 쓰지 않고 풀었다.

우선 문제에서 해결하기위해 포인트를 나열해보자면,

1. 팰린드롬 문자열은 데칼코마니처럼 한쪽에 문자를 완성하였다면, 가운데를 기점으로 반대로 출력을 하면 완성된다.
2. 정답이 여러 개일 경우에는 사전 순이므로, 입력을 받으면 문자열대로 나열한다.
3. 문자열이 홀수개일 경우와 짝수개일 경우를 나누어서 생각한다.
4. 문자열이 짝수개라면 (AABB 4개, AABBCC 6개), 모든 문자들이 짝수개이어야한다.
5. 문자열이 홀수개라면 단 하나의 문자만 홀수개이고 다른 모든 문자는 짝수개이어야 한다. (AABCC; B만 1개, ABBCACBBA; A만 3개)

5가지를 생각하며 문제를 해결해보자.

 

#전체 길이가 홀짝판별
#짝수 -> 모든 문자의 갯수가 짝수
#홀수 -> 하나의 문자는 홀수개이어야하고 나머진 모두 짝수개
receive_word = input()
#받은 문자열을 정렬
receive_word = ''.join(sorted(receive_word))
#문자열이 홀수라면 True, 짝수라면 False
is_odd = len(receive_word) % 2 == 1
#데칼코마니처럼 찍어내기 위해서 홀수인 문자열을 저장하기 위한 변수
odd_word = ''
#팰린드롬이 가능하다면 True, 불가능하다면 False
can_pall = True


#문자열 정리
word_dic = {}
before_word = ''

for i in range(0, len(receive_word)):
    #현재 단어가 이전단어와 다른경우
    if before_word != receive_word[i]:
        if before_word != '':
            #이전단어의 갯수가 홀수인지 짝수인지 확인한다
            #홀수라면,
            if word_dic[before_word] % 2 == 1:
                if is_odd:
                    # 홀수갯수의 문자가 처음이라면 False로 바꾼다.
                    # 홀수문자를 저장한다.
                    is_odd = False
                    odd_word = before_word
                else:
                    #문자열이 짝수일때, 홀수갯수의 문자가 존재하거나,
                    #문자열이 홀수일때, 홀수갯수의 문자가 두 개 이상일때
                    can_pall = False
                    break
        #이전단어를 저장한다.
        before_word = receive_word[i]
        #현재 단어를 dictionary에 추가한다.
        word_dic[receive_word[i]] = 1
        
    #이전 단어가 현재 단어와 같다면 갯수 1을 추가해준다.
    else:
        word_dic[receive_word[i]] += 1

#만약 is_odd가 안변하면 마지막단어가 홀수
if (len(receive_word) % 2 == 1) == is_odd == True:
    odd_word = receive_word[-1]

#결과값 생성
result = ''
for key in word_dic.keys():
    result += key * (word_dic[key] // 2)

#팰린드롬 문자열을 만들 수 있는지 확인하고 출력한다.
if can_pall:
    if odd_word == '':
        #데칼코마니처럼 result를 출력 후 반대로 출력
        #짝수인 경우, 반대로만 출력
        print(result+result[::-1])
    else:
        #홀수인 경우, 홀수인 문자 하나만 가운데에 두고 반대로 출력
        print(result+odd_word+result[::-1])
else:
    print("I'm Sorry Hansoo")