[프로그래머스] 모음사전 / 완전탐색 / python

문제

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

프로그래머스

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

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

제한사항

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

word 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번째 단어입니다.

풀이

아이디어

생각 난 거는 가능한 모든 조합을 만들어보자는 거였다

카테고리도 완전탐색이니..

파이썬은 collection 라이브러리에 순열, 조합 다 구현이 되어있으니 편하게 구현 할 수 있다

중복순열을 이용해 가능한 모든 조합을 만든다

정렬한 후, 제시된 단어의 인덱스 +1 하면 구현 끝이다

코드

from itertools import product

def solution(word):
    vowels = ['A', 'E', 'I','O','U']
    dict = []
    for i in range(5):
        for v in product(vowels, repeat = i+1):
            dict.append(''.join(v))    
    dict.sort()
    return dict.index(word)+1

print(solution("AAAE"))

개수가 별로 많지 않기 때문에 아묻따 와다다 만들어서 하는게 가능하겠지만

주먹구구 식으로 말고 다른 방법으로 해보고 싶어서 고민고민하다가 찾아봤다

1. 중복순열을 이용
2. dfs를 이용
3. 규칙을 이용

다른 풀이

dfs를 이용한 풀이

dictionary에 A, AA, ,,, , AAAAA를 넣으며 DFS를 돈다

길이가 5일 때 AAAAE, AAAAI , ,,,, AAAAU와 같이 한글자씩 넣어준다

가능한 모든 경우를 만들어 준 후, index +1 을 리턴

def solution(word):
    answer = 0
    dictionary = []
    words = 'AEIOU'

    def dfs(cnt, w):
        # 최대 길이는 5
        if cnt == 5:
            return
        for i in range(len(words)):
            dictionary.append(w + words[i])
            dfs(cnt+1, w + words[i])
    dfs(0, '')
    return dictionary.index(word) + 1

규칙을 이용한 풀이

https://blog.naver.com/jungs-note/223230753043

[프로그래머스/Python] 모음사전

https://leedakyeong.tistory.com/m/entry/Python-프로그래머스-코딩테스트-연습-완전탐색-모음사전

[Python - 프로그래머스] 코딩테스트 연습 > 완전탐색 > 모음사전

세상엔 많은 천재들이 있다는 것을 다시 한번 느끼며..