문제 설명 (링크)
위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다.
대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다.
이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.
상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.
대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.
같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.
예를 들어 1 위에 있던 손가락을 0 으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다.
단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.
숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해주세요.
풀이
function solution(numbers) {
// i >> j 로 가는 경우의 가중치 map
const map = [
[1, 7, 6, 7, 5, 4, 5, 3, 2, 3],
[7, 1, 2, 4, 2, 3, 5, 4, 5, 6],
[6, 2, 1, 2, 3, 2, 3, 5, 4, 5],
[7, 4, 2, 1, 5, 3, 2, 6, 5, 4],
[5, 2, 3, 5, 1, 2, 4, 2, 3, 5],
[4, 3, 2, 3, 2, 1, 2, 3, 2, 3],
[5, 5, 3, 2, 4, 2, 1, 5, 3, 2],
[3, 4, 5, 6, 2, 3, 5, 1, 2, 4],
[2, 5, 4, 5, 3, 2, 3, 2, 1, 2],
[3, 6, 5, 4, 5, 3, 2, 4, 2, 1],
]
// 특정 위치에서의 가중치를 기록하기 위한 dictionary
let dictionary = new Array(10).fill().map(_ => new Array(10).fill(null));
// 초기값 (왼손 = 4, 오른손 = 6, 가중치 = 0)
dictionary[4][6] = 0;
dictionary[6][4] = 0;
// 숫자 순회
for (let number of numbers) {
number = Number(number); // string >> number 처리
// 해당 숫자에 대한 기록용 dictionary 선언
const newDict = new Array(10).fill().map(_ => new Array(10).fill(null));
// 이전 기록된 dictionary 조회
dictionary.forEach((row, idx1) => {
row.forEach((el, idx2) => {
if (el !== null) { // 값이 할당 된 경우
const value = el; // 이미 할당된 값
if (idx1 === number || idx2 === number) { // 이미 가려는 자판에 손가락이 있는 경우
const resultValue = newDict[idx1][idx2] ? Math.min(newDict[idx1][idx2], value + 1) : value + 1; // 이미 기록된 가중치에 1을 더한 값(제자리 누름)
newDict[idx1][idx2] = resultValue;
newDict[idx2][idx1] = resultValue;
} else {
const weightValue1 = map[idx1][number]; // idx1 위치가 움직일 경우 가중치
const weightValue2 = map[idx2][number]; // idx2 위치가 움직일 경우 가중치
// 기록된 가중치와, 더해질 가중치의 합, 이미 기록된 값이 있다면, 작은 값으로 기록
const resultValue1 = newDict[idx1][number] ? Math.min(newDict[idx1][number], value + weightValue2) : value + weightValue2;
const resultValue2 = newDict[idx2][number] ? Math.min(newDict[idx2][number], value + weightValue1) : value + weightValue1;
// 더해진 가중치를 기록
newDict[idx1][number] = resultValue1;
newDict[number][idx1] = resultValue1;
newDict[number][idx2] = resultValue2;
newDict[idx2][number] = resultValue2;
}
}
})
})
dictionary = newDict;
}
// dictionary를 순회해서 할당된 값이 있는 경우, 최소값을 찾아 return
return Math.min(...dictionary.map(el => Math.min(...el.filter(el => Number(el)))).filter(el => Number(el)));
}결과
