[프로그래머스 84512 파이썬] 모음사전 (level 2, 완전 탐색)

알고리즘 유형 : 완전 탐색
풀이 참고 없이 스스로 풀었나요? : O

https://school.programmers.co.kr/learn/courses/30/lessons/84512

소스 코드(파이썬)

import sys
input = sys.stdin.readline

def solution(word):
    stack = ["A"]
    # 사전 순서 상 다음 알파벳을 찾기 위한 딕셔너리
    # key : 알파벳 value : 사전 순서 상 다음 순서 알파벳
    nextAlphabet = {"A": "E", "E": "I", "I": "O", "O": "U"}
    prev = None
    count = 0
    
    while True:
        count += 1
        word_frag = ''.join(stack) # 단어
        
        if word_frag == word: # 찾는 단어와 같으면 탈출 후 count 리턴
            break
        
        # 단어의 길이가 5 미만이면, A 추가해주기(사전 순서 상 다음 단어가 됨)
        # 단어 길이가 5라면, 맨 마지막 알파벳을 빼주고 다음 순서 알파벳을
        # 추가해준다. 단, 맨 마지막 알파벳이 U라면 U가 아닐때까지
        # 계속계속 빼준다.
        if len(stack) < 5:
            stack.append("A")
        elif len(stack) == 5:
            prev = stack.pop()
            
            while prev == "U":
                prev = stack.pop()
            
            stack.append(nextAlphabet[prev])
        
    return count

풀이 요약

1. 스택을 활용했다.

   사전 1번 단어부터 하나씩 단어를 만들어가는데, 그 단어가 찾는 단어와 같을 때까지 반복문을 실행한다.

2. 반복문 안에서 단어를 만드는 로직을 살펴보자. (스택에 쌓여있는 알파벳들이 하나의 단어를 이룸)

   우선 스택의 길이가 5보다 작은 경우, 맨 뒤에 알파벳 "A"를 추가해준다. 이렇게 만든 것이 사전 순서 상 바로 다음 순서의 단어가 된다.

   스택의 길이가 5인 경우, 맨 마지막 알파벳을 pop해준다. 그리고 사전 순서 상 그 알파벳의 다음 알파벳을 append해준다. (이를 위해 딕셔너리를 정의. pop한 알파벳이 key, 그 것의 다음 순서 알파벳이 value)

   그런데 pop한 알파벳이 "U"라면, 그 다음 순서 알파벳이 없는데 어떡할까?

   이럴 때는 그 이전의 알파벳을 다음 순서 알파벳으로 바꿔주면 된다.

   예를 들어 AAAAU의 다음 순서 단어는 AAAE, 그 다음이 AAAEA... 이런 식이다.

   그런데 AAAUU처럼 U를 빼고 나서, 그 이전의 알파벳 또한 U인 경우가 있다.

   그래서, 아예 반복문으로 U가 안나올때까지 U를 계속 빼준다.

   U를 다 빼고 그 이전의 A를 빼내고 나서 E를 추가해주면 그 다음 순서 단어인 AAE가 된다.

배운 점, 어려웠던 점

• 머릿 속으로만 계속 생각하다가, 마땅한 풀이가 안 떠올라서 종이에 직접 1번 단어부터 쭉 나열해보았고 거기서 해법을 생각해냈다. 풀이가 바로 안 떠오르는 문제를 풀 때는 직접 경우의 수를 적당히 나열해보면서 풀이를 생각해내는 방법을 적극 기용해야겠다.