문제 설명

휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.

예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.

같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.

이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.

1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.

단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.

문제 풀이

function solution(keymap, targets) {
    var answer = [];
    
    const newKeymap = keymap.map((key) => key.split(''));
    
    const newTargets = targets.map((target) => target.split(''));
       
    let count;
    let check;
    
    for(let i = 0 ; i < newTargets.length; i++) {
        count = [];
        for(let j = 0; j < newTargets[i].length; j++) {
            check = [];
            for(let k = 0; k < newKeymap.length; k++) {                       
                const findTarget = newKeymap[k].findIndex((key) => key === newTargets[i][j]);
                
                if(findTarget != -1) {
                    check.push(findTarget + 1);
                }
                
            }
            
            if(check.length === 0) {
                count.push(-1);
            }
            else {
                count.push(Math.min.apply(null, check));
            }
            
        }
        
        if(count.includes(-1)) {
            answer.push(-1);
        }
        else {
            answer.push(count.reduce((acc,cur) => acc + cur));
        }
   
        console.log(`정답`, answer);
    }
    
    return answer;
}

count와 check는 answer에 넣을 값들의 배열과 target 계산 후 나오는 자판을 몇 번 눌렀는지를 확인하기 위함이다.
둘다 처음에는 배열이 아닌 숫자로 카운트를 해보고자 했으나 -1이 나왔을 때 예외 처리를 하는 것에서 많은 자원이 소모될 것이라는 생각이 들었고 미리 모든 값들을 배열 형태로 저장해두고 한번에 계산하게 된다면 시간적으로도 빨라질 것이라고 예상하여 이런 방식을 채택하게 되었다.

실제로도 이런 방식을 채택한 후로 1~11번 정답의 시간이 3ms 정도 줄어들었음을 확인하였으며 -1을 처리하는 방식에서 배열에 있는지 없는지만을 확인하게 되므로 처리가 간단해져 알고리즘을 작성하는데 편해졌다.

아쉬운 점은 count와 check로 동시에 2개의 배열을 할당하여 자원을 소비하게 되기 때문에 현재 케이스는 최대 100개지만 한번에 10만개 이상의 케이스가 들어오게 되었을 때 현재의 for문을 여러번 반복하는 방식으로는 처리에 시간이 매우 오래 걸릴 것으로 예상된다.
map구조, hashTable 등의 자료구조를 사용하여 데이터 조회, 저장 방식을 간단화 하여 처리할 수 있지 않을까?