99클럽 코테 스터디 16일차 TIL + 완전 탐색

[오늘의 학습 키워드 및 문제]
- 프로그래머스의 "모음사전" 문제를 풀었다.
- 오늘 주제는 완전 탐색이다.
- 조건에 맞는 모든 조합을 생각하려고 하니 라이브러리를 쓸 수도 있지만 재귀함수로 구현했다.

[나의 코드]

def solution(word):
    vowels = ['A', 'E', 'I', 'O', 'U']
    vowel_dict = {}
    idx = 1
    
    def find(current, length):
        nonlocal idx
        
        if length > 5:
            return
        
        if current:
            vowel_dict[current] = idx
            idx += 1
        
        for vowel in vowels:
            find(current + vowel, length + 1)
    
    find("", 0)
    return vowel_dict[word]

혹시 몰라서 딕셔너리로 풀었는데 아래 배열로 푼 거랑 속도 차이가 많이 나지 않았다.

일단 종료 조건은 단어의 길이가 5를 넘는다면 return을 하도록 하였다.
그리고 빈 문자열이 아니라면 딕셔너리에 키와 값을 넣어준다.

그리고 그다음이 가장 중요한 부분이다.
재귀함수로 현재 단어에 다음 모음을 붙여서 새로운 단어를 만든다.
길이도 하나씩 늘려준다.

참고로 return 문을 만나더라도 다른 재귀 호출이 계속되기 때문에 프로그램이 완전히 종료되지 않는다.
여기서 nonlocal 키워드에 대해서 설명을 해두자면,

함수 내에서 전역 변수를 수정하려면 global 키워드를 사용해야 한다. 그러나 global 키워드는 함수 내에서 전역 변수를 선언할 때 사용한다. 하지만 여기서 idx는 함수 내부에서 정의된 변수이므로 nonlocal 키워드를 사용한다. 즉, 함수 내부에서 외부 함수의 변수를 수정하려면 nonlocal 키워드를 사용해야 된다.

def solution(word):
    vowels = ['A', 'E', 'I', 'O', 'U']
    all_vowels = []
    
    def find(current, length):
        if length > 5:
            return
        
        all_vowels.append(current)
        
        for vowel in vowels:
            find(current + vowel, length + 1)
    
    find("", 0)
    all_vowels.sort()
    return all_vowels.index(word)

다음은 딕셔너리 말고 배열로 구현해 봤다.
로직은 위와 같은데, 마지막에 정렬을 해줘야 한다. 단어가 늘 사전순으로 생성된다는 보장이 없기 때문이다.
정렬하기 싫으면 딕셔너리로 풀면 된다.

[오늘의 회고]
- 재귀는 오늘도 어려웠다. 머리로 쉽게 안 그려져서 그런갑다.
- 찾아본 바로는 product 라이브러리를 불러와서 풀 수 있으나 재귀로 풀어보길 권장한다.
- 완전 탐색은 재귀 형태의 문제가 많기 때문이다. 끝!