프로그래머스 | Words Made up of Vowels 문제풀이

문제 링크

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

프로그래머스

 

문제 접근 방식

순열을 사용해서 모든 경우를 나열한 다음에 정렬 함수를 사용해서 사전을 만들 수도 있고,

재귀함수를 사용해서 정렬 없이 바로 사전을 만들 수 있을 것 같다.

 

모든 경우의 수가 m 일때, 전자의 방식은 정렬을 해줘야하므로 O(mlogm) 시간이 걸리는 반면,

재귀를 통해 바로 구하는 경우에는 O(m) 의 시간이 걸린다. 

후자의 방식이 코드를 작성하는데 많은 어려움이 있을 것 같지 않아서 재귀함수를 사용해서 문제풀이를 진행했다.

 

처리 방법

재귀 함수에서는 현재 단어를 사전에 먼저 넣어주고, 해당 단어에 다른 모음을 추가해서 재귀함수를 수행하도록 구현했다.

 

재귀함수

1. 현재 단어의 길이가 6 이상이면 함수를 종료한다(탈출 조건)

2. 현재 단어를 사전에 넣는다.

3. 모음을 순회한다

    3.1. 현재 단어에 모음을 추가해서 단어를 생성한다.

 

코드

vowels=['A','E','I','O','U']
def make_dictionary(word,dictionary):
    if len(word)>=6:
        return

    dictionary.append(word)
    for i in range(5):
        make_dictionary(word+vowels[i],dictionary)


def solution(word):
    dictionary=[]
    for i in range(5):
        make_dictionary(vowels[i], dictionary)

    return dictionary.index(word)+1

 

 

회고

재귀 함수 두번째 문제