프로그래머스 - 조이스틱 (Javascript)

---

문제 설명

프로그래머스의 테스트케이스 추가로, 이전에 풀었던 솔루션 코드가 통과되지 않아 다시 재작성 했습니다.

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

• 🔼 다음 알파벳
• 🔽 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
• ◀ 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
• ▶ 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 “JAZ”를 만들 수 있습니다.

• 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
• 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
• 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
  따라서 11번 이동시켜 “JAZ”를 만들 수 있고, 이때가 최소 이동입니다.
• 만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

---

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

---

입출력 예

name	return
“JEROEN”	56
“JAN”	23

---

풀이 과정

예전에 백준에서 비슷한 문제를 풀어본적 있던 것 같다.
아래의 아스키 코드를 활용하면 될 것 같고, 거리계산을 효율적으로 하면 풀 수 있을 것 같다.

는 나의 헛된 망상이자 꿈이었다….ㅋ

1. 우선 String을 배열로 split한다

2. 그리고 각 배열의 요소들을 charCodeAt을 통해 아스키 코드로 변환한다

3. 상하 이동 경우의 수 (최소값)

   ⇒ Math.min(num - 65, 91 - num)

   바닥값(65)과 천장값(91) 사이의 거리 중에 가장 가까운 것을 선택하면 된다.

4. 좌우 커서 이동의 경우의 수 (최소값)

5. 상하 이동 + 좌우 이동 계산

---

소스코드 (초기 풀이)

이 방식은 2021년에 풀었던 방식인데, 현재 변경된 테스트케이스로는 통과가 되지 않는다.
그리고 다시 보니.. 로직도 굉장히 하드코딩 구현 방식이라 좋지 못한 것 같다.

function solution(name) {
  let answer = 0;
  let arr = name.split('');
  arr = arr.map((el) => el.charCodeAt(0));
  let indexes = [];
  // 상하 이동값부터 계산
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== 65) {
      answer += Math.min(Math.abs(65 - arr[i]), Math.abs(91 - arr[i]));
      // A가 아닌 값들의 index를 관리하기 위한 indexes 배열을 만들어 활용했음
      indexes.push(i);
    }
  }
  // 처음 값이 A가 아닐 경우에는 어차피 커서 좌우 이동에 영향을 주지 않기 때문에 그냥 indexes에서 빼줘도 된다.
  if (arr[0] !== 65) {
    indexes.shift();
  }
  // 만약에 길이가 하나면, 굳이 아래의 모든 케이스를 돌려볼 필요가 없다.
  // 따라서 우측으로 이동하는게 더 나은지, 좌측으로 이동하는게 더 나은지만 판단하면 된다.
  if (indexes.length === 1) {
    let left = Math.abs(arr.length - indexes[indexes.length - 1]);
    let right = indexes[0];
    answer += Math.min(left, right);
    return answer;
  }

  // 이제 좌우값 체크
  // #Case1 : 우측으로만 갈 때
  let case1 = arr.length - 1;

  // #Case2 : 좌측으로만 갈 때
  let case2 = Math.abs(arr.length - indexes[0]);

  // #Case3 : 우측으로 시작했는데 한 번 꺾을 때
  let case3 = 0;
  // 만약에 첫 값이 A가 아니라면 그 값을 건너 뛰어서 시작해야된다.
  let i = arr[0] !== 65 ? 1 : 0;
  let case3BCount = 0;
  while (true) {
    if (case3BCount !== 0 && arr[i + 1] === 65) {
      break;
    } else if (case3BCount === indexes.length - 1) {
      break;
    }
    if (arr[i + 1] !== 65) {
      case3BCount++;
      i++;
    } else {
      i++;
    }
  }
  // 한번 갔다가 같은만큼 돌아오기 때문에 2를 곱해준다.
  case3 = i * 2 + arr.length - indexes[case3BCount];

  // #Case4 : 좌측으로 시작했는데 한 번 꺾을 때
  let case4 = 0;
  let j = arr[arr.length - 1] !== 65 ? arr.length : arr.length - 1;
  let case4BCount = 0;
  while (true) {
    if (case4BCount !== 0 && arr[j - 1] === 65) {
      break;
    } else if (case4BCount === indexes.length - 1) {
      break;
    }
    if (arr[j - 1] !== 65) {
      case4BCount++;
      j--;
    } else {
      j--;
    }
  }
  case4 = (arr.length - j) * 2 + indexes[indexes.length - case4BCount - 1];

  return answer + Math.min(case1, case2, case3, case4);
}

---

소스코드 (New)

훨씬 간결하고, 오류가 없는 코드다.
사실 계속 오류가 나는 테스트케이스가 뭔지 몰라서.. 해결하기 위해 꽤 많은 시간을 투자했다ㅜ

이 풀이 방법은 거의 모든 경우의 수를 다 탐색한다.

1. 우측 정방향으로만 갔을 때

2. 좌측 역방향으로만 갔을 때

3. 정방향, 역방향으로 시작하되, 중간에 한 번 유턴을 할 때

   ⇒ 이 부분에서 거의 모든 경우의 수를 탐색한다.

function solution(name) {
  let answer = 0;
  const chars = [...name].map((char) => char.charCodeAt());
  const length = chars.length;
  let upDown = 0;
  let leftRight = chars.length - 1; // 우측 정방향으로 한번에 쭉 가는 경우
  let straight, back, endPoint;
  // 위에서 초기값을 정방향으로 쭉 갔을 때의 거리로 줬기 때문에,
  // 이 반복문 안에서는 가다가 한 번 꺾는 경우만 계산해주면 된다.
  for (let distance = 0; distance < length; distance++) {
    // 1. distance는 이번 순회에서 이동해야 하는 거리를 의미한다. 첫 시작은 0이다.
    // 최초에 우측으로 시작하는 것이 아니라 좌측으로 시작되는 경우도 있기 때문이다.
    // 2. 가장 구하기 쉬운 upDown부터 구한다.
    upDown += Math.min(91 - chars[distance], chars[distance] - 65);
    if (chars[distance + 1] !== 65) continue;
    // 종결 지점은 distance+1이다. (distance=0일 때 0을 찍고 뒤돌아 0의 다음까지 이동해야 하기 때문)
    endPoint = distance + 1;
    // 하지만 다음 값(distance+1)이 A라면 유턴할 때 굳이 A까지 돌아올 필요는 없기에,
    // enpoint가 A는 무시하도록 A의 끝까지 반복문을 통해 endPoint를 이동시킨다.
    while (leftRight < length && chars[endPoint] === 65) endPoint++;
    // 1. 첫 시작이 우측 정방향인 경우
    straight = distance * 2 + (length - endPoint);
    // 2. 첫 시작부터 역방향으로 꺾어 간 경우
    back = (length - endPoint) * 2 + distance;
    leftRight = Math.min(leftRight, straight, back);
  }
  answer = upDown + leftRight;
  return answer;
}

주석 제거

function solution(name) {
  let answer = 0;
  const chars = [...name].map((char) => char.charCodeAt());
  const length = chars.length;
  let upDown = 0;
  let leftRight = length - 1;
  let straight, back, endPoint;
  for (let distance = 0; distance < length; distance++) {
    upDown += Math.min(91 - chars[distance], chars[distance] - 65);
    if (chars[distance + 1] !== 65) continue;
    endPoint = distance + 1;
    while (leftRight < length && chars[endPoint] === 65) endPoint++;
    straight = distance * 2 + (length - endPoint);
    back = (length - endPoint) * 2 + distance;
    leftRight = Math.min(leftRight, straight, back);
  }
  answer = upDown + leftRight;
  return answer;
}

---

풀이 설명

distance와 endPoint

distance는 우측으로 이동할 거리,
endPoint는 유턴해서 돌아올 때 멈춰야 할 지점이다.

위의 경우에는 distance=1, endPoint=2다.

1만큼 우측으로 이동했다가 → 유턴해서 다시 좌측으로 1만큼 이동한 뒤에 → 배열 끝에서부터 endPoint까지 이동해야 한다는 뜻이다.

따라서 이 경우는 (1*2) + 배열의 길이 - endPoint가 될 것이다. (1만큼 왕복이동)

---

if (chars[distance + 1] !== 65) continue

왜 이러한 조건문을 걸었는지 그림을 통해 설명해보도록 하겠다.
위의 예시와 같은 상황이라고 가정해보자.

위 사진처럼 B가 여러개 연속되어 있을 때가 문제라고 생각했다. 여기에

if (chars[distance + 1] !== 65) continue

코드가 없었다면 아래와 같이 굳이 불필요한 점진적 순회를 했을 것이다. (뒷 부분의 이동거리 = 알바펫 개수인 이유는, 첫 번째에서 끝으로 넘어갈 때의 이동거리도 포함된 것이기 때문)

위 그림에서도 알 수 있듯, 변경대상(A가 아닌 것들)들이 붙어있는데 이를 하나하나 점진적으로 순회 할 필요는 없다. 우리가 이 반복문에서 체크하고자 하는 것은, 결국 A를 뛰어넘어 endPoint까지 가기 위해 좌측으로 돌아 가는 것이 빠른지, 우측으로 돌아 가는 것이 빠른지이기 때문이다.

따라서, 변경대상(!A)들이 즐비해 있을 경우에는, A가 나타날 때까지 endPoint를 우측으로 이동시키는 것이 더 효율적이다. (더 쉽게 생각하자면, 주어진 배열이 [B,B,B,B,B,B,B,B,B,B,B,B,B]였는데 현재 조건문이 없었다고 가정해보면 된다)

---

straight & back의 공식 설명

문제에서 가장 중요한 부분이다.
사실 이 공식은 이전 풀이 때도 사용했었지만, 이전에는 처음부터 바로 좌측으로 이동하는 경우를 생각하지 못했던 것 같다.

먼저 짚고 넘어가야 할 부분은 straight가 처음에는 우측으로 이동했다가 유턴을 하는 경우고, back은 처음에 바로 좌측으로 이동했다가 중간에 다시 유턴을 하는 경우다. 바래 아래의 사진들을 살펴 보며 이해해보도록 하자.

우선 위와 같이 반복문의 시작점(distance)은 0이다. 그리고 endPoint는 0+1인 1이다.

따라서 처음 움직여야 하는거리는 0이고, 뒤로 돌아서 endPoint까지 도달하는 데 까지의 거리는 5다. 즉, 이는 처음부터 좌측으로 스트레이트로 이동한 것과 같은 결과를 도출한다.

straight = 0 * 2 + (length - 1) = 5

back = (length - 1) * 2 + 0 = 10

다음 반복문에서는 위와 같은 경우가 발생한다.

distance는 반복문에 의해 ++되어 1로 늘어난 상태다. 하지만, endPoint가 가리키는 대상이 A이기 때문에 A가 끝날 때까지 endPoint를 이동시켜줘야 한다. (굳이 A가 있는 곳까지 이동할 필요가 없음)

따라서 반복문 안에 설정된 while문으로 인해 위의 사진과 같은 형태가 될 것이다.

이 경우에는 아래와 같은 식이 도출된다.

straight = (1 * 2) + (length - 3) = 5

back = (length - 3) * 2 + 1 = 7

직접 한 번 손으로 따라 가보면 위의 식이 가리키는 값이 어떻게 도출 된 것인지, 그리고 맞는지의 여부를 쉽게 파악할 수 있을 것이다.

straight의 경우 → 우측으로 1 → 다시 좌측으로 1 → 맨 뒤로 돌아가서 3만큼 이동 = 5만큼 이동

back의 경우 → 바로 끝으로 가서 좌측으로 3만큼 이동 → 다시 3만큼 우측으로 이동하여 처음으로 돌아옴 → 1만큼 이동

이러한 과정을 계속 반복하면 최적화된 커서 좌우 이동 경우의 수를 모두 도출할 수 있다!

---