문제

위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다.

대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다.

• 이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.
• 상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.
• 대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.
• 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.

예를 들어 1 위에 있던 손가락을 0 으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다.
단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.

숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해주세요.

Greedy로 생각했던 코드 (오답)

const keyboard = [
    [3, 1], [0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]
];

function getWeight(src, dest) {
    let weight = 0;
    let srcCoord = keyboard[src], destCoord = keyboard[dest];
    let absDist = [Math.abs(srcCoord[0] - destCoord[0]), Math.abs(srcCoord[1] - destCoord[1])];
    
    if(src === dest) return 1;
    
    //0이 포함되어 있지 않다면 (대각선에 있다는 거고) 0이 포함되게 만든다.
    if(!absDist.includes(0)) {
        const need = Math.min(...absDist);
        weight += need * 3;
        absDist = absDist.map(d => d - need);
        if(absDist[0]) weight += absDist[0] * 2;
        else weight += absDist[1] * 2;
    }
    //같은 열이나 행에 있는 경우
    else {
        weight += 2 * Math.max(...absDist);
    }
    
    return weight;
}

function solution(numbers) {
    let left = 4, right = 6;
    var w = 0;
    
    for(let i=0; i<numbers.length; i++) {
        const next = ~~numbers[i];
        const leftWeight = getWeight(left, next);
        const rightWeight = getWeight(right, next);
        if(leftWeight < rightWeight) {
            w += leftWeight;
            left = next;
        } else {
            w += rightWeight;
            right = next;
        }
    }
    
    return w;
}

풀이

아이디어

• 처음에는 Greedy로 생각해서 했다가(현재 지점에서 당장 최솟값을 선택해 나가는 것) 틀리는 걸 보고 완전탐색을 해야겠다고 생각했다. 하지만, 완전탐색을 하기에는 숫자 자릿수가 최대 100,000개였고, 이거에 대해서 완전탐색을 하게 된다면 2의 10만승을 다 찾아봐야 하는 꼴이다. (당연히 시간 초과 뜰 것)
• 완전탐색을 써야하지만 시간 초과가 너무 분명하다면, 시간 초과가 나지 않게 완전 탐색을 하란 뜻이고, 그 말은 곧 DP(Dynamic Programming) 기법을 쓰란 말이 된다.

DP 적용

• 메모이제이션용 배열을 다음과 같은 형식으로 생성해야 한다.
  • cache[idx][L][R]: numbers의 idx번째 숫자를 눌렀을 때의 왼쪽 손가락과 오른쪽 손가락의 위치에 따른 가중치의 최솟값 기록
  • 또한 cache는 모두 Infinity로 초기화 해준다.
  • 그리고 시작점이 왼쪽 손가락 4, 오른쪽 손가락 6이므로 cache[0][4][6] = 0으로 설정한다.
• 또, 숫자패드의 한 숫자에서 다른 숫자까지 손가락을 옮길 때 최소 가중치를 기록하여 distBoard에 저장한다.
• 이제 numbers의 숫자 하나하나 순회하면서 다음과 같은 로직을 수행한다.
  • 새로 추가해야 하는 숫자를 num이라고 하자.
  • 0부터 10까지의 이중 for loop 내부에서 다음 로직을 수행한다.
    • 왼쪽 손가락, 오른쪽 손가락이 같은 위치에 있으면 안 되므로 i==j인 경우나, 이전의 캐시값이 Infinity인 경우는 스킵한다.
    • 이전의 캐시값이 Infinity가 아니라면, 왼쪽 손가락을 num으로 옮겼을 때와 오른쪽 손가락을 num으로 옮겼을 때를 각각 현재 자리에서의 캐시와 비교하고, 현재 자리에서의 캐시가 더 클 경우 현재 자리에서의 캐시값을 업데이트 해준다.
• 우리가 리턴해야 할 것은 맨 마지막 캐시테이블에서의 최솟값이다.

코드

const keyboard = [
    [3, 1], [0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]
];

function getWeight(src, dest) {
    let weight = 0;
    let srcCoord = keyboard[src], destCoord = keyboard[dest];
    let absDist = [Math.abs(srcCoord[0] - destCoord[0]), Math.abs(srcCoord[1] - destCoord[1])];
    
    if(src === dest) return 1;
    
    //0이 포함되어 있지 않다면 (대각선에 있다는 거고) 0이 포함되게 만든다.
    if(!absDist.includes(0)) {
        const need = Math.min(...absDist);
        weight += need * 3;
        absDist = absDist.map(d => d - need);
        if(absDist[0]) weight += absDist[0] * 2;
        else weight += absDist[1] * 2;
    }
    //같은 열이나 행에 있는 경우
    else {
        weight += 2 * Math.max(...absDist);
    }
    
    return weight;
}

function solution(numbers) {
    let left = 4, right = 6;
    let distBoard = Array(10).fill(0).map(elem => Array(10).fill(0));
    for(let i=0; i<10; i++) {
        for(let j=0; j<10; j++) {
            distBoard[i][j] = getWeight(i, j);
        }
    }
    
    let cache = Array.from({ length: numbers.length + 1 }, () =>
    Array.from({ length: 10 }, () => new Array(10).fill(Infinity))
  );
    cache[0][4][6] = 0;
    
    for(let idx=0; idx<numbers.length; idx++) {
        const num = ~~numbers[idx];
        
        const prevCache = cache[idx];
        const nowCache = cache[idx+1];
        
        for(let i=0; i<10; i++) {
            for(let j=0; j<10; j++) {
                const prevValue = prevCache[i][j];
                if(i==j || prevValue == Infinity) continue;
                
                if(nowCache[num][j] > prevValue + distBoard[i][num])
                    nowCache[num][j] = prevValue + distBoard[i][num];
                
                if(nowCache[i][num] > prevValue + distBoard[j][num])
                    nowCache[i][num] = prevValue + distBoard[j][num];
            }
        }
    }
    
    return Math.min(...cache[numbers.length].flat().flat());
}