1213. [Python]팰린드롬 만들기

1. 문제

 

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

1213번: 팰린드롬 만들기

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 구현
• 문자열

 

3. 파이썬 코드

 

word = input()
word_length = len(word)
# 들어온 길이가 1인 경우 무조건 word 출력
if word_length == 1:
    print(word)
# 2인 경우 0번 인덱스와 1번 인덱스가 다른지 확인
elif word_length == 2:
    if word[0] == word[1]:
        print(word)
    else:
        print("I'm Sorry Hansoo")
# 그 외의 경우
else:
    # 인풋값을 우선 정렬
    sorted_word = sorted(word)
    # 딕셔너리 생성 => 갯수 세기 위해
    sorted_dict = {}
    # 딕셔너리에 값을 넣으며 갯수를 세는 중
    for i in sorted_word:
        if i in sorted_dict:
            sorted_dict[i] += 1
        else:
            sorted_dict[i] = 1
    # 만약 길이가 짝수인 경우
    if word_length %2 == 0:
        answer = ""
        # 딕셔너리 key, value 를 순환하며
        for k,v in sorted_dict.items():
            # value 값이 홀수 인 경우 대칭이 될 수 없다.
            if v % 2 == 1:
                print("I'm Sorry Hansoo")
                answer = ""
                break
            # 짝수인 경우
            else:
                # value값이 1,1 인경우 1번 나왔기 때문에 answer에 k 한번만 더해준다.
                if v//2 == 0:
                    answer = answer + k
                # 그 외의 경우 몫만큼 곱한걸 더해준다.
                else:
                    answer = answer + k*(v//2)
        # 만약 변수가 공백이면 0부터 끝까지와 끝에서부터 0까지를 더해서 출력해준다.
        if answer != "":
            print(answer+answer[::-1])
    # 홀수인 경우
    else:
        answer = ""
        # 홀수인 경우 짝수인 경우와는 다르게 홀수의 갯수를 체크해줘야 하기 때문에 변수를 넣어준다.
        cnt = 0
        # 짝수일때와 마찬가지로 반복문 시행
        for k,v in sorted_dict.items():
            # 홀수의 경우 홀수일때 홀수의 갯수를 체크해줘야 한다.
            if v % 2 == 1:
                cnt += 1
                # 홀수일때 check 라는 변수에 key 값을 넣어준다
                check = k
                # 이제 딕셔너리의 value 값을 -1 해줘서 짝수로 바꿔준다.
                sorted_dict[k] -= 1
                # 만약 바꾼 딕셔너리 값이 0 인경우 무시하고 그 외인 경우 갯수를 2로나눈 몫만큼 곱해서 answer 변수에 넣어준다.
                if sorted_dict[k] == 0:
                    pass
                else:
                    answer = answer + k*(sorted_dict[k]//2)
            # 짝수인 경우
            else:
                # 몫이 0인 경우 갯수가 1번 나왔다는 의미이므로 (사실상 불필요) k 한개만 더해준다
                if v//2 == 0:
                    answer = answer + k
                else:
                    answer = answer + k*(v//2)
            # 만약 cnt 값이 2보다 큰 경우 펠린드롬이 될 수 없다.
            if cnt >= 2:
                print("I'm Sorry Hansoo")
                answer = ""
                check = ""
                break
        if answer != "":
            print(answer+check+answer[::-1])

 

4. 문제를 풀고난 후 생각

 

• 숫자로 팰린드롬 정렬하는 것은 많이 접해봐서 문자로 된 문제가 있길래 풀어볼려고 시도했다. 한 2일 정도 소요하여 문제를 해결했던 것 같다.
• 문자로 어떻게 구현을 해야할지 고민을 제일 많이했고, 짝수일때, 홀수일때로 구분을 지어서 구현을 해야겠다고 생각을 했다.
• 짝수인 경우는 구현자체가 간단했다. 불필요한 반복문을 돌지 않기위해서 input으로 값이 들어오며 딕셔너리를 통하여 값의 갯수를 체크해줬다. 그리고 그 값들이 홀수인 경우 그냥 break 처리를진행 하였다.
• 그 이유는 짝수인 경우 중앙값이 없기 때문에 문자의 갯수가 홀수가 나올 경우 대칭이 완성될 수 없기 때문에 이렇게 생각을 진행하였다. ( ex => "AAAB", "AB", "AAABBB" 등 대칭으로 만들 수가없다 )
• 홀수인 경우에서 조건이 조금 많았던 것 같다.
• 홀수인 경우 문자의 값이 홀수인 갯수가 2개 이상이 될 경우 break문을 사용하여 탈출을 걸어줬는데, AAABBCC 로 A는 3개 B는 2개 C는 2개 가되면 ABCACBA 로 대칭을 만들 수 있지만 ABC or AAABBBCCC 등 각 문자의 갯수가 홀수개가 되는 경우는 대칭을 만들 수 없기 때문에 cnt라는 변수를 사용하여 홀수의 갯수를 체크하여 2이상이 되는경우 break를 걸어줬다. ( 짝수개는 나올 수 없다. => 길이가 홀수이기 때문에 3 2 1 or 2 1 1 등 합이 짝수가 나온다. )
• 출력을 하는 부분에 있어서 answer 이라는 변수에 짝수, 홀수를 나눠서 결과를 출력하게 선언해줬다.
• 모든 조건을 통과하여 answer이라는 변수에는 "ABAB"라는 문자가 들어왔으면 "AB" 만 넣어주고 출력하는 부분에서 "ABBA"로 출력이 되게끔 설정했다.
• 홀수는 "AAABB" 라는 문자가 들어올 경우 "AB"를 answer이라는 변수에 넣고 check 를 사용하여 중앙에 넣을 문자를 넣어줬다. 그리고 출력할때 "AB" + "A" + "BA" 가 되도록 설정해줬다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 구현
• 문자열