알고리즘 문제 풀이/프로그래머스

[프로그래머스] 모음 사전- python[ Permutation ]

잘잔디 2023. 9. 13. 12:41

[level 2] 모음 사전 - 84512

문제 링크

성능 요약

메모리: 10.1 MB, 시간: 0.93 ms

구분

코딩테스트 연습 > 완전탐색

채점결과

Empty

문제 설명

사전에 알파벳 모음 '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번째 단어입니다.

나의 풀이

1.입력받은 문자의 길이별 + 문자별 조건식?
2.BruteForce니까 로직만 짜서 1씩 증가? <- 이래도 되는게 가장 큰 수 해봐야 5^5임 시간초과는 안날걸
2번으로 진행해보도록 하고, 로직은 어떻게 하느냐가 문제일듯

중복 순열을 사용해야 하는데 중복순열은 2일전에 풀었던 소수 찾기 문제에서 약간의 변형을 가해 순열코드를 중복 순열 코드로 변경하였다. 사실 이 문제를 어제 풀다가 중간에 수업을 다녀온 후 영어 회화에 대한 심각한 필요성을 느껴(수업이 영어수업 + 영어 발표임) 영어 공부를 급하게 했었던... 

global case,answer,sel,check
case = ['A', 'E', 'I', 'O', 'U']

def perm(depth,length):
    global case, answer,sel,check
    if depth == length:
        answer.append(''.join(sel))
        return
        
    for i in range(length):
            sel[depth] = case[i]
            perm(depth+1, length)
    
def solution(word):
    global answer,sel,check
    answer = []
    for i in range(5):
        sel = ['' for _ in range(5)]  
        check = [0 for _ in range(5)]  
        perm(i,5)
    answer.sort()
    return answer.index(word)+1

파이썬 라이브러리 product를 사용한 코드

from itertools import product
def solution(word):
answer = []
for i in range(1,6):
for v in product(["A","E","I","O","U"],repeat = i):
answer.append("".join(v))
answer.sort()
return answer.index(word)+1