Lv_2. 모음사전

* Programmers _위클리 챌린지 5주차 문제입니다.

* 언어는 javascript 를 선택했습니다.

 

1. 문제

1) 모음사전

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

 

2) 제한사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

 

2. 알고리즘! 생각해보자

처음에는 문제가 이해가지 않아 주르륵 나열해보니

약간의 규칙을 찾을 수 있었습니다.

1: A	<-> 781	782(=1+781): E
2: AA	<-> 156	158(=2+156): AE
3: AAA	<-> 31	34(=3+31): AAE	AAI	AAO	AAU
4: AAAA	<-> 6	10(=4+6): AAAE	AAAI	AAAO	AAAU
5: AAAAA	<-> 1
6: AAAAE
7: AAAAI
8: AAAAO
9: AAAAU

 

word는 1~5자리인데, _ _ _ _ _ 각 자리수 별로

첫번째 자리는 781 

두번째 자리는 156

세번째 자리는 31

네번째 자리는 6

다섯번째 자리는 1

씩 차이가 나는 것을 확인할 수 있었습니다.

 

그런데 입출력 예시와 값을 비교해보면, 위의 값 만으로는 해결되지 않는 것을 확인할 수 있습니다.

예를들어, "EIO" 의 경우 1189 이 출력되어야 하는데, 

위의 값으로 계산하면, (781 * 1) + (156 * 2) + (31 * 3) =  781 + 312 + 93 = 1186 으로 정답과 3 차이가 납니다.

 

지금까지 계산한 것은 A <-> E 의 차이라는 것을 놓친 것입니다.

그래서 시작값인 A(1), EA(1), EIA(1) 의 3가지 경우를 추가하면, 정답과 일치하게 됩니다.

(이 값은 결국 word 의 길이가 되겠더라구요!)

 

저는 그래서 코딩할 때 각 경우를 vertical, horizontal 값을 계산하는 것이라고 생각하고

아래와 같은 코드를 도출하였습니다.

answer = getHorizonLen(word) + getVerticalLen(word)

 

3. 해결 코드

function solution(word) {
    var answer = getHorizonLen(word) + getVerticalLen(word);
    return answer;
}

function getVerticalLen(word) {
    const wordList = ['A', 'E', 'I', 'O', 'U'];
    let result = 0;
    word.split('').forEach((item, idx) => {
        const wordIdx = +wordList.indexOf(item);
        const multiplyVal = [781, 156, 31, 6, 1];
        result += wordIdx * multiplyVal[idx];
    });
        
    return result;
}

function getHorizonLen(word) {
    return word.length;
}

 

4. 문제해결 능력 UP! 되짚어보기

• 같은 알고리즘인데, 한 줄 풀이

function solution(words) {
    return words.split('').reduce((r, c, i) => r + [781, 156, 31, 6, 1][i] * ['A', 'E', 'I', 'O', 'U'].indexOf(c) + 1, 0);
}

• DFS

function solution(word) {
    function dfs(p) {
        if (p.length > 5) return;

        answer[p] = cnt;
        cnt++;
        for (let w of "AEIOU") {
            dfs(p + w);
        }
    }

    const answer = {};
    let cnt = 0;
    dfs("");
    return answer[word];
}

 

5. References