위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다.
대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다.
예를 들어 1 위에 있던 손가락을 0 으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다.
단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.
숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해주세요.
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;
}
cache[idx][L][R]
: numbers
의 idx
번째 숫자를 눌렀을 때의 왼쪽 손가락과 오른쪽 손가락의 위치에 따른 가중치의 최솟값 기록cache
는 모두 Infinity
로 초기화 해준다.cache[0][4][6] = 0
으로 설정한다.distBoard
에 저장한다.numbers
의 숫자 하나하나 순회하면서 다음과 같은 로직을 수행한다.num
이라고 하자.i==j
인 경우나, 이전의 캐시값이 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());
}