[프로그래머스] Lv.2 모음사전 (완전탐색)

모음사전

• 최대 시간복잡도: O(n^5)
  • 5 + 5*5 + 5*5*5 + 5*5*5*5 + 5*5*5*5*5 = 3905
  • 최대 시간복잡도는 n^5 이지만, 워낙 최대 횟수가 적어서 완전탐색으로 빠르게 풀기로 했다.

풀이 1 (완전탐색, for 문)

function solution(word) {
    const str = ['','','','',''];
    const alphabet = ['A','E','I','O','U'];
    const n = 5;
    let cnt = 0;

    for(let i0=0; i0<n; i0++) {
        str[0] = alphabet[i0];
        cnt++;
        if(check(word, str)) return cnt;

        for(let i1=0; i1<n; i1++) {
            str[1] = alphabet[i1];
            cnt++;
            if(check(word, str)) return cnt;

            for(let i2=0; i2<n; i2++) {
                str[2] = alphabet[i2];
                cnt++;
                if(check(word, str)) return cnt;

                for(let i3=0; i3<n; i3++) {
                    str[3] = alphabet[i3];
                    cnt++;
                    if(check(word, str)) return cnt;

                    for(let i4=0; i4<n; i4++) {
                        str[4] = alphabet[i4];
                        cnt++;
                        if(check(word, str)) return cnt;
                    }
                    str[4] = '';
                }
                str[3] = '';
            }
            str[2] = '';
        }
        str[1] = '';
    }
}

function check(word, str) {
    return str.join('') === word ? true : false;
}

풀이 2 (완전탐색, 재귀 recursive)

const alphabet = ['A','E','I','O','U'];
let cnt = 0;
let N = 5;

function solution(word) {
    const str =  ['','','','',''];

    return loop(0, str, word);
}

function loop(step, str, word) {
    if(step === N) return -1;

    for(let i=0; i<N; i++) {

        str[step] = alphabet[i];
        cnt++;

        if(check(word, str)) return cnt; 

        let out = loop(step+1, str, word);
        if(out !== -1) {
            return cnt;
        }

        str[step] = ""; 
    }
    return -1;
}

function check(word, str) {
    return str.join('') === word ? true : false;
}