프로그래머스 - Level 1. 대충 만든 자판 / JavaScript (js)

문제설명

문제분석

이 문제는 targets를 순회하며 각 요소(target) 문자열이 keymap을 통해 최소 몇 번만에 만들어지는 지 구하는 문제입니다. 이때 target을 구할 수 없다면 -1을 담으면 됩니다. keymap과 targets 배열의 길이가 100 이하이므로 완전탐색을 이용해 문제를 해결할 수 있습니다.

이해하기 쉽게 코드작성하기

function solution(keymap, targets) {
    const answer = new Array(targets.length).fill(-1);
    
    // targets을 탐색
    for(let i = 0; i < targets.length; i++) {
        const target = targets[i];
        let count = 0;
        // target의 각 문자를 탐색
        for(let j = 0; j < target.length; j++) {
            const str = target[j];
            // keymap의 각 요소 중 target[j]를 포함하는 문자의 minimum index 구함
            const min = Math.min(...keymap.map(x => {
                const idx = x.indexOf(str);
                return idx === -1 ? Infinity : idx + 1;
            }));
            if(min === Infinity) {
                count = -1;
                break;
            }
            count += min;
        }
        answer[i] = count;
    }
    
    return answer;
}

이렇게 접근하면 각 타겟의 문자열을 기준으로 keymap의 각 요소 중 가장 작은 index를 찾습니다. 이 로직을 살펴보면 keymap의 각 요소를 매번 서치하는 문제를 발견할 수 있습니다. 이 부분을 memoization을 통해 해소하고, 메소드를 적절히 섞어주면 다음과 같이 변경할 수 있습니다.

 

function solution(keymap, targets) {
    const memo = {};
    
    keymap.forEach((key) => key.split("").forEach((alphabet, i) => {
        memo[alphabet] = (memo[alphabet] || Infinity) < i + 1 ? memo[alphabet] : i + 1;
    }));

    return targets.map(target => {
        const sum = target.split("").reduce((a, t) => a += memo[t], 0);
        return sum && sum < Infinity ? sum : -1;
    });
}