프로그래머스 - 고득점 kt - 완전탐색 - 모음사전
Level2
📖Problems
사전에 알파벳 모음 ‘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번째 단어입니다.
🔍Approach
- 무엇을 사용할까? (순열/조합/중복순열)
- 중복순열(product)
- 왜?
- 중복을 허용하여, 가능한 한 모든 경우의 수를 봐야되기 때문(A, AA, AAA, AAAA 등 모두 중복순열임)
PRODUCT(중복순열) : 중복을 포함해 모든 경우의 수를 구하는 법
1 2 3
from itertools import product list = ["012", "abc", "!@#"] pd = list(product(list))
🚩My submission
- 무식하게 보일 수 있겠지만, 가능한 모든 조합을 다 탐색한 후, 리스트에 append한다.
- 리스트를 정렬한다.
- 매개변수로 전달받은
word가 있는 인덱스값 + 1을 return한다.
1차
1
2
3
4
5
6
7
8
9
10
11
12
from itertools import product
def solution(word):
answer = 0
c_list = ['A','E','I','O','U']
dictionary = []
for i in range(1, len(c_list)+1):
dictionary.append(''.join(list(product(c_list, repeat = i))))
dictionary.sort()
return dictionary.index(word)+1
TypeError: sequence item 0: expected str instance, tuple found
2차
1
2
3
4
5
6
7
8
9
10
11
12
13
from itertools import product
def solution(word):
answer = 0
c_list = ['A','E','I','O','U']
dictionary = []
for i in range(1, len(c_list)+1):
for j in product(c_list, repeat = i):
dictionary.append(''.join(j))
dictionary.sort()
return dictionary.index(word)+1
이 풀이 말고도
나름대로 규칙을 찾아보려 노력했으나 잘 되지 않았다…
A - E - I - O - U
A -> 1 = 15
AA -> 1+1 = 2
AAA -> 1+1+1 = 3
AAAA -> 1+1+1+1 = 4
AAAAA -> 1+1+1+1+1 = 5
AAAAE -> 1+1+1+1+2 = 6
AAAAI -> 1+1+1+1+3 = 7
AAAAO -> 1+1+1+1+4 = 8
AAAAU -> 1+1+1+1+5 = 9
AAAE -> 1+1+1+2+5 = 10
AAAI -> 1+1+1+3+5 = 11
AAAO -> 1+1+1+4+5 = 12
AAAU -> 1+1+1+5+5 = 13
AAE -> 1+1+2+5+5 = 14
AAI -> 1+1+3+5+5 = 15
AAO -> 1+1+4+5+5 = 16
AAU -> 1+1+5+5+5 = 17
AE -> 1+2+5+5+5 = 18
AI -> 1+3+5+5+5 = 19
AO -> 1+4+5+5+5 = 20
AU -> 1+5+5+5+5 = 21
————
EA -> 2+1+5+5+5 =
EAA
EAAA
EAAAA
EAAAE
EAAAI
EAAAO
EAAAU
EAAE
EAAI
EAAO
EAAU
EAE
EAI
EAO
EAU
EE
E
EO
EU
🚩Others submission
1
2
3
4
5
6
7
8
9
10
11
def solution(word):
answer = 0
dic = ['A', 'E', 'I', 'O', 'U']
li = [5**i for i in range(len(dic))]
for i in range(len(word)-1,-1,-1):
idx = dic.index(word[i])
for j in range(5-i):
answer += li[j]*idx
answer+=1
return answer
1
2
3
4
5
6
7
8
def solution(word):
char = {'A': 0, 'E': 1, 'I': 2, 'O': 3, 'U': 4}
answer = len(word) # A를 0으로 두었기 때문에 길이로 초기화 필요
re = (((5 + 1) * 5 + 1) * 5 + 1) * 5 + 1 # 781
for i in word:
answer += re * char[i] # 첫 문자가 무슨 글자로 시작하는지
re = (re - 1) // 5
return answer
- 이 코드에 대한 이해는 완벽히 되지 않아,, 링크 걸어놓은 블로그를 참고하는 것이 좋을 것 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(word):
answer = 0
word_list = []
words = 'AEIOU'
def dfs(cnt, w):
if cnt == 5:
return
for i in range(len(words)):
word_list.append(w + words[i])
dfs(cnt+1, w + words[i])
dfs(0,"")
return word_list.index(word)+1
word_list에 A, AA, AAA, AAAA, AAAAA을 넣으면서 DFS를 돌다가cnt = 5일 때 되돌아가면 AAAAE, AAAAI, AAAAO, AAAAU를 넣다가AAAE, AAAEA, AAAEI … 를 넣게 된다. 이런 식으로 완전 탐색 진행- 우리가 찾는
word의 순서는word_list에서word의 인덱스 + 1
💡TIL
- 중복순열 product (
from itertools import product)- product(리스트, repeat = 조합하고 싶은 개수)
- 이 문제는 product말고도 규칙을 찾아 풀 수도 있고 dfs로도 풀 수 있었다. 규칙을 찾아낸 사람들은 정말 대단한 것 같고 dfs는 전에 한 문제와 비슷하지만 여전히 재귀가 헷갈려서 이해에 어려움이 있었다