[프로그래머스] 조이스틱

문제

조이스틱

https://school.programmers.co.kr/learn/courses/30/lessons/42860

 

 

풀이

설명

조이스틱 조작 횟수의 최솟값을 구하는 문제입니다.

 

조작 횟수는 수직 이동 횟수 + 수평 이동 횟수입니다.

 

수직 이동 횟수는 문자열을 순회하며 각 문자가 기본 문자와 얼마나 차이나는지를 구하면 됩니다.

 

신경써야 할 부분은 수평 이동 횟수인데요.

수평으로 이동하는 시나리오는 총 두 가지입니다.

1. 한 쪽 방향으로 쭉 이동할 경우
2. 한 쪽 방향으로 이동하다가 특정 지점에서 반대쪽 방향으로 이동할 경우

 

2번을 고려하기 위해서, 기본 문자인 A가 아니면서 가까운 두 문자의 인덱스 i와 j를 찾아 첫 문자에서 i까지 오른쪽으로 이동한 횟수와 j까지 왼쪽으로 이동한 횟수를 구해야 합니다.

둘 중 더 작은 구간을 먼저 다녀오고, 이후 더 큰 구간을 가야 값이 더 작아집니다. 따라서 작은 구간 길이 * 2 + 큰 구간 길이를 구해 지금까지 구한 최소 횟수와 비교하면 됩니다.

 

아래는 이름이 "ABABAAAAAAAABA"일 때, 수평 이동 횟수의 최솟값입니다.

수평 이동 시나리오 2번을 고려한 수평 이동 횟수 예시

 

예시 코드

function solution(name) {
  const DEFAULT_CHARACTER = "A";
  const LAST_ALPHABET = "Z";

  const length = name.length;
  let verticalMoves = 0;

  // 1. 수직 이동 횟수 계산
  for (const char of name) {
    verticalMoves += Math.min(
      char.charCodeAt(0) - DEFAULT_CHARACTER.charCodeAt(0),
      LAST_ALPHABET.charCodeAt(0) - char.charCodeAt(0) + 1
    );
  }

  // 2. 수평 이동 횟수 계산
  let horizontalMoves = length - 1;
  for (let i = 1; i < length; i++) {
    if (name[i] !== DEFAULT_CHARACTER) continue;

    let j = i + 1;
    while (j < length && name[j] === DEFAULT_CHARACTER) {
      j++;
    }

    const rightMoves = i - 1;
    const leftMoves = length - j;
    const smallerMoves = Math.min(rightMoves, leftMoves);
    const largerMoves = Math.max(rightMoves, leftMoves);
    horizontalMoves = Math.min(horizontalMoves, smallerMoves * 2 + largerMoves);

    i = j; // 연속된 A 구간 건너뛰기
  }

  return verticalMoves + horizontalMoves;
}

 

현재 코드는 수평 이동 시나리오 1번과 2번을 한 번에 계산하고 있습니다.

또한 불필요한 반복을 줄이기 위해 i가 "A"가 아닌 문자 바로 다음 인덱스를 가리키고 있습니다.