파이썬(Python) 알고리즘 문제풀이 모음사전 [프로그래머스 / 문자열]

출처) 프로그래머스 Facebook

문제 설명

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

 

 

제한사항

word의 길이는 1 이상 5 이하입니다.
word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

 

 

입출력 예시

s	result
"AAAAE"	6
"AAAE"	10
"I"	1563
"EIO"	1189

 

 

입출력 예 설명

입출력 예 #1

사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

입출력 예 #2

"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

입출력 예 #3

"I"는 1563번째 단어입니다.

입출력 예 #4

"EIO"는 1189번째 단어입니다.

 

 

풀이 코드

재귀 함수에 for 문을 적절히 사용해서 새로운 문자를 만들어내고, 이를 매개변수로 해서 계속해서 재귀 함수를 호출하는 방식으로 풀이했다. 재귀 함수의 매개 변수가 걔속해서 갱신되며 호출할 수 있는지를 항상 생각하자. 따로 점화식은 없었고 종료 조건을 어떻게 해야할까 고민을 했는데, 우리가 원하는 문자를 찾을 때 또는 만든 모음 뭉치를 담아두는 리스트에서 우리가 원하는 문자를 찾는 경우를 종료 조건으로 하기에는 "I" 가 1563 번째 이기 때문에 찾기도 전에 StackOverFlow 예외를 만날 것 같았다. 따라서 갱신되는 문자열 길이가 5일 경우 뒤로 돌려 문자를 갱신하는 방식으로 구현했다.

 

아래는 첫 번째 풀이 코드

def recursion(now_word, target_word, wort_list):
    vowel = ['A', 'E', 'I', 'O', 'U]

    # 갱신된 문자열과 찾는 문자열이 같다면 모음 사전 기록을 중지한다.
    if now_word == target_word:
        return

    # 갱신된 문자열의 길이가 5라면 이전으로 돌아가기 위해 기록을 중지한다.
    if len(now_word) == 5:
        return

    # 모음이 5개이므로 5만큼 반복하면서 새로운 문자열을 만들어 모음사전에 기록 후 갱신된 문자열을 넘기면서 재귀 호출한다.
    for i in range(5):
        new_word = now_word + i
        word_list.append(new_word)
        recursion(new_word, target_word, word_list)


def solution(word):
    word_list = []

    recursion('', word, word_list)

    # 재귀 함수가 모두 호출되었다면 모음 사전에 기록되어있을 word 의 인덱스 번호를 찾아 + 1 후 반환한다.
    return word_list.index(word) + 1

 

문제를 풀었지만, 문자열을 더하는 연산 등이 마음에 안들어서 개선한 코드
len(now_word) 대신 level 변수 사용 (근데 len 도 O(1) 이라 편한대로 사용하면 될 듯)
문자열 = 문자열 + 문자열 대신 ''.join([합칠 문자, 합칠 문자]) 로 개선

def recursion(now_word, target_word, word_list, level):
    if now_word == target_word:
        return

    if level == 5:
        return

    for i in ['A', 'E', 'I', 'O', 'U]:
        new_word = ''.join([now_word, i])
        word_list.append(new_word)
        recursion(new_word, target_word, word_list, level + 1)


def solution(word):
    ... 중략 ...