[JS] 숫자 타자 대회

문제 요약

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

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

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

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

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

---

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
  • numbers는 아라비아 숫자로만 이루어진 문자열입니다.

입출력 예

numbers	result
"1756"	10
"5123"	8

 

접근 방법

 

단순하게 bfs 형식으로 풀이하면 가짓수가 두 배로 늘어납니다.

left, right에 대해서 꼭 그리디하게 따르지 않기 때문에 모든 경우에 대해서 왼손에서 이동한 경우와 오른손에서 이동한 경우를 동시에 생각해줘야하기 때문에 매 분기마다 두 배씩 늘어나게 됩니다.

 

numbers의 길이 <= 100,000
^ 이 조건 때문에 엣지 케이스에서 절대 통과될 수 없습니다.

 

 

이런 경우는 16번 ~ 20번에 도달했을 때 시간 초과가 되어 정답을 도출해낼 수 없습니다.

결론적으로 각 분기별로 눌러야 하는 숫자에 대해서 dp를 적용해서 해결해야만 합니다.

#이나 *이 나올 일이 없기 때문에 기껏해봐야 10 X 10의 2차원 배열이거든요.

 

 

정답 코드

function getWeight(target) {
    if (target === 0) return { r: 3, c: 1 };
    else return { r: Math.floor((target - 1) / 3), c: (target - 1) % 3 };
}

function solution(numbers) {
    // distMap: 키패드 이동할 때 드는 가중치 ex) [0][1] = 7; [0][2] = 6;
    const distMap = Array.from({ length: 10 }, (_, i) => {
        const { r: iR, c: iC } = getWeight(i);
        return Array.from({ length: 10 }, (_, j) => {
            const { r: jR, c: jC } = getWeight(j);
            const [diffR, diffC] = [Math.abs(iR - jR), Math.abs(iC - jC)];
            return 3 * Math.min(diffR, diffC) + 2 * Math.abs(diffR - diffC) || 1;
        })
    });
    
    // weights: 이동에 드는 최솟값 가중치 모음.
    let weights = distMap.map(v => v.map(_ => Infinity));
    weights[4][6] = 0;
    weights[6][4] = 0;
    
    for (let number of numbers) {
        number = Number(number);
        const temp = weights.map(v => v.map(_ => Infinity));
        
        weights.forEach((row, iR) => {
            row.forEach((weight, iC) => {
                // 이전에 눌렀던 지점에서 실행. ex) loop-1: [4][6] || [6][4]
                if (weight !== Infinity) {
                    if (iR === number || iC === number) {
                        temp[iR][iC] = Math.min(temp[iR][iC], weight + 1);
                        temp[iC][iR] = Math.min(temp[iC][iR], weight + 1);
                        return;
                    }
                    
                    // loop-1 [4][6]일때) [4][1] = Math.min([4][1], [4][6] + [6][1])
                    // loop-1 [6][4]일때) [6][1] = Math.min([6][1], [6][4] + [4][1])
                    // 그래서 leftVal에 rightW넣고, rightVal에 leftW 넣기!
                    const leftW = distMap[iR][number];
                    const rightW = distMap[iC][number];
                    const leftVal = Math.min(temp[iR][number], weight + rightW);
                    const rightVal = Math.min(temp[iC][number], weight + leftW);

                    temp[iR][number] = leftVal;
                    temp[iC][number] = rightVal;
                    temp[number][iR] = leftVal;
                    temp[number][iC] = rightVal;
                }
            });
        });
        weights = temp;
    }
    
    return Math.min(...weights.flat(1));
}

 

 

dp가 생각이 어려운데 결국엔 점화식이 비슷비슷 거기서 거기라는 생각이 드네요 요즘엔

좀만 더하면 빨리 풀 수 도 있을 것 같습니다. 이번에는 bfs에 집착하다가 한세월 풀었네요.

그럼 이만!