[Algorithm] 숫자 타자 대회

📋 문제

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

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

 

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

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

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

제한사항

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

 

입출력 예

"1756"	10
"5123"	8

✏️ 첫번째 오답을 봤던 풀이 (정답풀이는 아래!)

처음 시도했던 재귀를 이용한 접근방법으로 오답세례를 경험했다. 스텍이 너무 많이 쌓여서인지 런타임에러도 발생했다.(그럴만해..?)

 

우선 처음으로 board라는 변수를 하나 선언했다. 이 board에는 이차원배열을 할당했는데 이는 인덱스를 번호로 가지고 외부 배열의 요소로는 배열로 위치를 가진다. ex) 1이라는 숫자는 가로 1번째, 세로 1번째 -> [1, 1]

 

그 다음 calcDist라는 함수를 작성했다. board를 바탕으로 번호 사이의 (가중치)를 구했다. 예를 들어 1번에서 3번으로 갈 때는 우방향으로 2회이기때문에 가중치는 4가 된다. 이를 숫자의 위치를 바탕으로 계산했다. 현재 숫자와 목표로 하는 숫자의 위치(board)를 거리로 계산했다. 각각 세로 가로의 떨어진 거리를 계산하고 두 수(가로, 세로)가 모두 0이상이면 대각선으로 갈 수 있기 때문에 +3을 해주고, 둘 중 하나만 존재할 경우 상하좌우로 이동하는 경우이므로 +2를 해준다.

 

이제 재귀를 돈다. 왼손 오른손 각각 목표로 하는 위치로 이동하여 가중치를 계산하도 만약 가중치가 동일하다면 재귀함수를 호출하고 그렇지 않으면 더 작은 숫자를 더해주고 현재 손의 위치를 변경시켜준다. 마지막 숫자까지 이 과정을 반복하면서 answer에 Math.min을 이용하여 최소값을 할당해줬다.

 

정답을 잘 나오는 것 같지만 런타임에러! -> 아마 재귀로 인한 스텍이 너무 많이 쌓여서로 예상한다.

 

⌨️ 첫번째 오답 코드 

function solution(numbers) {
  var answer = Infinity;

  const board = [
    [4, 2],
    [1, 1],
    [1, 2],
    [1, 3],
    [2, 1],
    [2, 2],
    [2, 3],
    [3, 1],
    [3, 2],
    [3, 3],
  ];

  const calcDist = (now, target) => {
    if (now == target) return 1;

    const [nowX, nowY] = board[now];
    const [targetX, targetY] = board[target];

    let x = Math.abs(nowX - targetX);
    let y = Math.abs(nowY - targetY);

    let cnt = 0;
    while (x || y) {
      if (x && y) {
        cnt += 3;
        x -= 1;
        y -= 1;
      } else if (x) {
        cnt += 2 * x;
        x = 0;
      } else if (y) {
        cnt += 2 * y;
        y = 0;
      }
    }
    return cnt;
  };

  const calc = (pos, idx, w) => {
    for (idx; idx < numbers.length; idx++) {
      const temp1 = calcDist(pos[0], numbers[idx]);
      const temp2 = calcDist(pos[1], numbers[idx]);
      if (temp1 === temp2) {
        calc([numbers[idx], pos[1]], idx + 1, w + temp1);
        calc([pos[0], numbers[idx]], idx + 1, w + temp2);
        return;
      } else if (temp1 < temp2) {
        w += temp1;
        pos[0] = numbers[idx];
      } else {
        w += temp2;
        pos[1] = numbers[idx];
      }
    }

    answer = Math.min(w, answer);
    return;
  };

  calc([4, 6], 0, 0);

  return answer;
}

 

 

✏️ 정답 풀이

재귀를 이용하다가 시간초과가 난다면 DP식으로 풀어야하지 않을까? 라는 생각을 했다. 하지만 왼손 오른손의 위치를 고려하는게 쉽지 않았다... dp 배열을 뜻하는 check의 정의는 다음과 같다. 삼차원배열로 모든값은 '-'로 초기화했다.

 

check[k][i][j] = k+1 번째 숫자에서 i 왼손, j 오른손일 때의 최소 가중치

 

위에서 풀었던 오답의 내용을 일부 사용했다.

board(변수) =  이차원배열로 인덱스를 번호로 가지고 각 값은 배열로 좌표를 가진다.

calcDist(함수) = 번호 사이의 가중치를 구하는 함수. board를 기준으로 두 수 사이의 거리를 구하고 거리를 계산해 가중치를 구함.

 

숫자(numbers)를 순회하면서 왼손 0~9 오른손 0~9인 경우를 확인했다.

 

첫번째로 계산할 수 있는 초기값이 있어야 하므로 check[0]에 대해 초기화를 시켜줬다.

 

• check[0][4][numbers[0]] = calcDist(6, numbers[0]);
• check[0][numbers[0]][6] = calcDist(4, numbers[0]);

 

같은 번호에 양손이 올라갈 수 없으므로 i와 j가 같은 경우는 continue 시켜주고 만약 check상 이전 값이 '-'인 경우 가능한 경우가 없기 때문에 continue 시켜줬다.

 

check[k-1][i][j]가 있는 경우 왼손 또는 오른손을 움직여 현재 번호를 누르는 상황을 계산했다. calcDist 함수를 각각 사용했다.

 

• check[k][i][현재숫자] -> 왼손이 현재숫자로 움직인 경우
• check[k][현재숫자][j] -> 오른손이 현재숫자로 움직인 경우

이를 반복하고 check배열(dp배열)에서 마지막 숫자에 해당하는 numbers.length-1번째를 확인한다. check[numbers.length-1] 마지막 숫자까지 모두 순회했을 때 왼손 i위치, 오른손 j 위치일 때의 가중치에 대한 값을 가지고 있다. 이를 순회하며 가장 작은 최소값을 구해줬다.

 

⌨️ 정답 코드 

function solution(numbers) {
  var answer = Infinity;

  const board = [
    [4, 2],
    [1, 1],
    [1, 2],
    [1, 3],
    [2, 1],
    [2, 2],
    [2, 3],
    [3, 1],
    [3, 2],
    [3, 3],
  ];

  const check = [...Array(numbers.length)].map(_ => [...Array(10)].map(_ => new Array(10).fill('-')));

  const calcDist = (now, target) => {
    if (now == target) return 1;

    const [nowX, nowY] = board[now];
    const [targetX, targetY] = board[target];

    let x = Math.abs(nowX - targetX);
    let y = Math.abs(nowY - targetY);

    let cnt = 0;
    while (x || y) {
      if (x && y) {
        cnt += 3;
        x -= 1;
        y -= 1;
      } else if (x) {
        cnt += 2 * x;
        x = 0;
      } else if (y) {
        cnt += 2 * y;
        y = 0;
      }
    }
    return cnt;
  };

  check[0][4][numbers[0]] = calcDist(6, numbers[0]);
  check[0][numbers[0]][6] = calcDist(4, numbers[0]);

  for (let k = 1; k < numbers.length; k++) {
    for (let i = 0; i < 10; i++) {
      for (let j = 0; j < 10; j++) {
        if (i === j) continue;
        if (check[k - 1][i][j] === '-') continue;

        const calc1 = check[k - 1][i][j] + calcDist(j, numbers[k]);
        if (check[k][i][numbers[k]] === '-') check[k][i][numbers[k]] = calc1;
        else check[k][i][numbers[k]] = Math.min(check[k][i][numbers[k]], calc1);

        const calc2 = check[k - 1][i][j] + calcDist(i, numbers[k]);
        if (check[k][numbers[k]][j] === '-') check[k][numbers[k]][j] = calc2;
        else check[k][numbers[k]][j] = Math.min(check[k][numbers[k]][j], calc2);
      }
    }
  }

  for (let i = 0; i < 10; i++) {
    for (let j = 0; j < 10; j++) {
      if (check[numbers.length - 1][i][j] === '-') continue;
      answer = Math.min(answer, check[numbers.length - 1][i][j]);
    }
  }

  return answer;
}