[완전탐색] 모음사전 - Python / JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

 

[문제 간단 요약]

• 알파벳 'A', 'E', 'I', 'O', 'U'로 구성된 단어들로 이루어진 사전으로,
• 단어는 길이 1~5로 만들때,
• 사전에서 주어진 단어가 몇 번째 위치인지 정하는 문제

[문제 해결 방안]

• 가능한 모든 단어를 생성하면서 순서를 체크하거나, 사전 전체를 구성해놓고 인덱스를 확인

[문제 해결 코드 - python(DFS 방식)]

def dfs(word, alpa, depth):
    global answer,cnt
    if alpa == word:
        answer = cnt
    if depth == 5:
        return
    for i in ['A','E','I','O','U']:
        cnt += 1
        dfs(word, alpa+i, depth+1)
    return -1

def solution(word):
    global answer, cnt
    answer = 0
    cnt = 0
    dfs(word, '', 0)
    return answer

 

[문제 해결 코드 - javascript (DFS 방식)]

function solution(word) {
    const word_alpha = ['A','E','I','O','U'];

    let answer = 0;
    let checked = false;

    function dfs(currentWord) {
        if (currentWord === word) {
            checked = true;
            return;
        }
        if (currentWord.length >= 5 || checked) return;
        for (let alpha of word_alpha) {
            if (checked) return;
            answer++;
            dfs(currentWord + alpha);
        }
    }

    dfs('');
    return answer;
}

 

 

[코드 개선점]

 

•  Python  코드도 JS 코드와 같이 checked 플래그를 사용하여 탐색을 중단하면 효율적\
  

[문제 해결 코드 - Python (itertools 활용)]

• product를 사용하여 길이 1~5 모든 가능 조합 생성
• 중복 계산 없이 단어를 한 번에 생성하므로 시간 복잡도 저하
• 재귀 사용이 없어 스택 오버플로우 문제 발생 x
• 메모리 사용에 있어 문제 발생 가능성 있음

from itertools import product

def solution(word):
    word_list = []

    for i in range(5):
        for comb in product("AEIOU", repeat=i+1):
            word_list.append("".join(comb))

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