꒰ྀི 14. 프로그래머스:: 모음 사전

사이트 문제도 첨부되지 않고 저작권 걸리는게 무서워서 프로그래머스로 회귀했다.

 

 

문제 요약

 

주어진 단어가 사전에서 몇 번째 단어인지 찾는 문제

 

접근 방법

1. 모든 단어 조합 생성
2. 사전 순으로 정렬
3. 정렬된 단어 목록에서 몇 번째 위치인지 찾기

 

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

    function generate(currentWord, length) {
        if (length > 5) return; 
        words.push(currentWord); 

        for (const vowel of vowels) {
            generate(currentWord + vowel, length + 1);
        }
    }

    generate('', 0);

    return words.indexOf(word);
}

 

사실 완전탐색으로 문제가 분류되어있어서 이렇게 풀었지만

이건 너무 비효율적일 것 같다.

 

사전 순 정렬 배열의 경우 애초부터 사전순으로 만들 수 있을 것이다.

가중치를 사용하면 더 근사한 풀이과정이 나온다.

function solution(word) {
    const vowels = ['A', 'E', 'I', 'O', 'U'];
    const weights = [781, 156, 31, 6, 1]; 

    let result = 0;

    for (let i = 0; i < word.length; i++) {
        const char = word[i];
        const index = vowels.indexOf(char);
        result += index * weights[i] + 1;
    }

    return result;
}

 

단어의 최대 길이가 5이기 때문에 각 자리마다 5^n의 가중치를 부여해주었다.