[Algorithms] [PGS] 키패드 누르기 / Level1

문제 정보

문제출처: 키패드 누르기: 프로그래머스
분류:

문제 파악

1. 왼손[1,4,7], 오른손[3,6,9]으로 정해져있다.
2. 가운데[2,5,8,0]를 어느 손으로 누를 것인가가 핵심이다.
3. 각각의 손가락 위치를 포인터로 설정해야 한다.

해결 방안

1. 키패드 위치에서 [2,5,8,0]까지의 거리를 객체로 담아두고 비교한다.
2. 현재 손의 위치를 확인하기 위해 위치가 변경될 때마다 포인터를 변경해준다.

function solution(numbers, hand) {
  var answer = "";
  // 각 키패드에서 가운데 키패드[2,5,8,0]까지의 거리
  // [0,1,2,3,4,5,6,7,8,9,*,#]이다.
  const move = {
    2: [3, 1, 0, 1, 2, 1, 2, 3, 2, 3, 4, 4],
    5: [2, 2, 1, 2, 1, 0, 1, 2, 1, 2, 3, 3],
    8: [1, 3, 2, 3, 2, 1, 2, 1, 0, 1, 2, 2],
    0: [0, 4, 3, 4, 3, 2, 3, 2, 1, 2, 1, 1],
  };
  let left = 10,
    right = 11; // 손가락 포인터

  for (let i = 0; i < numbers.length; i++) {
    if (numbers[i] === 1 || numbers[i] === 4 || numbers[i] === 7) {
      left = numbers[i];
      answer += "L";
    }
    if (numbers[i] === 3 || numbers[i] === 6 || numbers[i] === 9) {
      right = numbers[i];
      answer += "R";
    }
    if (
      numbers[i] === 2 ||
      numbers[i] === 5 ||
      numbers[i] === 8 ||
      numbers[i] === 0
    ) {
      const leftMove = move[numbers[i]][left];
      const rightMove = move[numbers[i]][right];
      if (leftMove < rightMove || (leftMove === rightMove && hand === "left")) {
        left = numbers[i];
        answer += "L";
      } else {
        right = numbers[i];
        answer += "R";
      }
    }
  }
  return answer;
}

코드 개선 방안

맨해튼 거리를 이용하면 move 에 수기로 작성한 거리를 코드적으로 해결할 수 있다.

function solution(numbers, hand) {
  var answer = "";

  const keypad = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
    ["*", 0, "#"],
  ];
  let left = "*";
  let right = "#";

  // 현재지점(x1, y1)에서 목표지점(x2, y2)까지의 거리를 구한다.
  const getDistance = function (from, to) {
    const [x1, y1] = convertKeypad[from];
    const [x2, y2] = convertKeypad[to];
    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
  };
  // keypad를 좌표로 변환한다.
  const convertKeypad = keypad.reduce((acc, prev, x) => {
    prev.forEach((number, y) => {
      acc[number] = [x, y];
    });
    return acc;
  }, {});
  for (let i = 0; i < numbers.length; i++) {
    if (numbers[i] === 1 || numbers[i] === 4 || numbers[i] === 7) {
      left = numbers[i];
      answer += "L";
    }
    if (numbers[i] === 3 || numbers[i] === 6 || numbers[i] === 9) {
      right = numbers[i];
      answer += "R";
    }
    if (
      numbers[i] === 2 ||
      numbers[i] === 5 ||
      numbers[i] === 8 ||
      numbers[i] === 0
    ) {
      const leftMove = getDistance(left, numbers[i]);
      const rightMove = getDistance(right, numbers[i]);
      if (leftMove < rightMove || (leftMove === rightMove && hand === "left")) {
        left = numbers[i];
        answer += "L";
      } else {
        right = numbers[i];
        answer += "R";
      }
    }
  }
  return answer;
}

코드 소요 시간 비교

(좌)손 계산 코드 / (우)개선한 코드

컴퓨터에 더 많은 계산을 맡겼기때문에 실행시간은 더 오래 걸렸다.
본 문제는 내가 직접 거리 계산을 한 순자가 [2,5,8,0] 4개라 금방 끝났지만
표본이 더욱 늘어나면 효율면에서 굉장한 차이가 날 것이다.
또한 거리는 상대적인 것으로 상황이 조금만 변화해도 거리계산을 다시 할 필요가 생길 것이다.
그렇기에 코드의 유지보수 측면에서도 직접 계산한 배열을 활용하는 것은 굉장히 비효율적이다.

신경쓸 부분

좀 더 컴퓨터에 계산을 맡길 수 있도록 코드를 설계하는 부분이 필요하다고 느꼈다.
또한 reduce, forEach 등 배열 고차 함수에 대해 다시 한번 개념을 확인할 필요가 있겠다.