프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간 초과(미구현)

from itertools import product

def solution(word):
    answer = 0
    # print(3**4)
    alphabets  = ['A','E','I','O','U']
    
#     for i in range(5):
#         for j in range(1,6):
#             for k in product(alphabets[:j], repeat=j):
#                 print(k)
        
#         break
    
    # for i in range(1,6):
    #     for i in product(alphabets, repeat=i):
    #         print(j)
            
            

#     for i in range(len(alphabets)):
#         for 
        # alphabets[i]
        
    # for i in range(5):
    #     for 
    
    for i in product(alphabets, alphabets, alphabets):
        print(i, end=" ")

    return answer

문제에서 'A','E','I','O','U' 글자들을 활용하여 모든 단어들을 검색한다는 점을 토대로 완전탐색을 구현하고자 하였습니다.

다중 for문과 순열 혹은 조합을 활용하고 싶었지만 'A', 'AA', 'AAA', 'AAAA', 'AAAAA', 'AAAAE', 'AAAAI', 'AAAAO', 'AAAAU', 'AAAE', 'AAAI'.. 등의 순서를 구현하는데 어려움이 있어 다른 풀이를 참고하였습니다.🐸🐸🐸

[다른 사람의 풀이1]

from itertools import product

def solution(word):
    words = []
    for i in range(1, 6):
        for c in product(['A', 'E', 'I', 'O', 'U'], repeat=i):
            words.append(''.join(list(c)))

    words.sort()
    return words.index(word) + 1

문제에서 요구하는 단어의 모든 경우의 수를 itertools의 product(중복조합)을 통해 구현하고 한번에 sort()하여 index를 찾아내는 방식입니다.

위 풀이의 핵심 포인트는 'A', 'AA', 'AAA', 'AAAA', 'AAAAA', 'AAAAE', 'AAAAI', 'AAAAO', 'AAAAU', 'AAAE', 'AAAI'.. 와 같은 순서는 컴퓨터가 문자열을 sort()하는 방식이므로 모든 단어의 조합을 구현한 뒤 정렬하는 것이였습니다.

모든 단어들을 구할 때, combinations(조합)에서 중복인 경우까지 포함하는 product를 활용할 수 있었습니다. 첫번째 for문을 뽑는 갯수 i로 이후 product로 중복조합을 뽑아 모든 경우의 수를 구할 수 있었습니다.

이번 문제를 통해 product(중복조합)의 활용법과 문자열 정렬이라는 포인트를 짚고 넘어갈 수 있었습니다.

[다른 사람의 풀이2]

def dfs(cnt, w,words,word_list):

    if cnt == 5:
        return 
    for i in range(len(words)):
        word_list.append(w + words[i])
        dfs(cnt+1, w + words[i],words,word_list)

def solution(word):
    answer = 0
    word_list = []
    words = 'AEIOU'
            
    dfs(0,"",words,word_list)
    
    print(word_list.index(word)+1)
    return word_list.index(word)+1

DFS로 구현한 풀이입니다. 깊이 우선 탐색 알고리즘의 경우 많이 다루어 보아 개념에 대해서는 알고 있지만 이를 활용한다는 생각을 하기 어려운 케이스였습니다.

복기하며 DFS를 적용할 수 있는 포인트를 짚어본다면 처음 'A', 'AA', 'AAA', 'AAAA', 'AAAAA', 'AAAAE', 'AAAAI', 'AAAAO', 'AAAAU' 뒤에 부터는 총 5글자임으로 return 하게됩니다. 이렇게 최대 크기 글자까지 재귀한 후 다음으로 append 되어 있던 'AAA'
가 다시 재귀되는 구조였습니다. 이번 문제를 통해 우선적으로 한 경로 끝까지 도달하는 DFS의 활용에 대해 다시 깨닫게 되었습니다.🐰🐰🐰

감사합니다.