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

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

프로그래머스

 

접근방법

 

1. 모든 중복순열을 만든다 

 

중복순열을 만들기 위해 product모듈을 사용한다

 

list(product(["A", "E", "I", "O", "U"], repeat = i))

 

해당 product 코드를 1부터 5까지 하면 

A, E, I, O ,U,

(A,A), (A,E),( A,I)...

(A,A,A), (A,A,E),( A,A,I)....

(A,A,A,A)....

(A,A,A,A,A)...

인 중복순열들이 만들어진다.

 

해당 중복순열들을 ,를 제거하고 하나로 합쳐서 result에 넣어준다

 

그리고 순서를 구하기 위해 sort를 해주고 받아오는 word의 순서를 구해준다.

 

from itertools import product

def solution(word):
    answer = 0
    
    result = list()
    for i in range(1, 6):
        li = list(product(["A", "E", "I", "O", "U"], repeat = i))
        for j in li:
            result.append(''.join(k for k in j))
    
    # 모든 중복순열 정렬
    result.sort()
    
    # 순서니까 index + 1
    answer = result.index(word) + 1
    return answer

 

해당 풀이는 단어가 5개라는 조건이 작아서 해당 방법으로 풀이할 수 있었다.

 

더 좋은 풀이는 없을까?

 

다른 풀이를 찾아보았다.

 

answer = 0
def DFS(string,word) :
    alphabets = ['A','E','I','O','U']
    global answer
    answer += 1
        
    if ( string == word ):
        return True
        
    if ( len(string) == 5) :
        return False
        
    for a in alphabets :
        if (DFS(string + a,word) == True) :
            return True

def solution(word):
    global answer
    alphabets = ['A','E','I','O','U']
    
    for a in alphabets :
        if (DFS(a,word) == True) :
            return answer

 

DFS를 이용한 풀이.

 

A,E,I,O,U를 DFS로 탐색을 합니다. 해당 탐색을 했을때 word와 일치하면 True를 리턴하게 되서 종료됩니다.

 

ex) word가 AAAAE라면

 

A  - 1

AA - 2

AAA - 3

AAAA -4

AAAAA -5 (이때 len이 5가되어서 FALSE를 return 하위 반복 X)

 

다시 AAAA로 올라가서
AAAAE를 탐색합니다 answer - 6

 

AAAAE는 word와 같기 때문에 True를 return 쭉 올라와서 answer - 6 DFS종료