[TIL #16] 모음사전

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

프로그래머스

 

DFS로 풀면 되는 문제긴 하다.

출제도 완전탐색을 통해 푸는 것을 의도했을 것이다.

 

의도대로 DFS를 통해 작성하면 다음과 같다.

function dfs(word, vowels, current, state) {
    if (state.found) return; // 목표 단어를 찾은 경우 탐색 종료

    for (let i = 0; i < vowels.length; i++) {
        const next = current + vowels[i];
        state.position++;

        // 현재 단어가 목표 단어와 같으면 위치 반환
        if (next === word) {
            state.found = true;
            return;
        }

        // 단어의 길이가 5 이하인 경우에만 계속 탐색
        if (next.length < 5) {
            dfs(word, vowels, next, state);
            if (state.found) return; // 목표 단어를 찾았으면 추가 탐색 종료
        }
    }
}

function solution(word) {
    const vowels = ['A', 'E', 'I', 'O', 'U'];
    
    // 상태 객체를 생성하여 position과 found를 관리
    let state = { position: 0, found: false };
    
    dfs(word, vowels, '', state);
    return state.position;
}

단어의 길이가 최대 5이기 때문에 완전탐색임에도 부담이 없다.

뭐 이대로 넘어갈 수도 있지만...

문제를 딱 보자마자 완전탐색이 아닌 다른 방법이 있을 것 같다는 느낌이 들었다.

 

각 모음엔 순서가 있다.

그리고 각 위치에 올 수 있는 수도 정해져 있다.

 

• 1번째 위치 : `` 1 + 5 + 5^2 + 5^3 + 5^4 = 781 ``
• 2번째 위치 : `` 1 + 5 + 5^2 + 5^3 = 156 ``
• 3번째 위치 : `` 1 + 5 + 5^2 = 31 ``
• 4번째 위치 : `` 1 + 5 = 6``
• 5번째 위치 : `` 1 ``

이런 식으로 개수가 미리 정의될 수 있기 때문에 이를 가중치로 사용할 수 있다.

이걸 코드로 다음과 같이 옮길 수 있다.

function solution(word) {
    const vowels = ['A', 'E', 'I', 'O', 'U'];
    const weights = [781, 156, 31, 6, 1]; // 각 위치별 가중치

    // 단어의 각 문자에 대해 가중치와 인덱스를 곱하고, 단어의 길이를 더함
    const position = word.split('').reduce((sum, cur, idx) => {
        return sum + weights[idx] * vowels.indexOf(cur);
    }, 0) + word.length;

    return position;
}

 

예시를 통해 확인해 보자.

 

"AAAAE"일 경우

``0 * 781 + 0 * 156 + 0 * 31 + 0 * 6 + 1 * 1 + 5 = 6``

 

"EIO"일 경우

``1 * 781 + 2 * 156 + 3 * 31 + 3 = 1189``

 

완전 탐색을 수행하는 것보다 훨씬 빠르고 간결하다.

 

확실히 이렇게 수학적 기법으로 문제를 풀 때 느껴지는 그러한 느낌이 있다.

검증된 수학적 이론을 통해 문제를 보다 쉽게 풀면,

정석대로 풀 때와 다른 느낌을 받는 건 나뿐일까...