[programmers] Lv2. 조이스틱 Javascript | protect-me

protect-me·2021년 5월 11일

programmers 알고리즘 알고리즘문제풀이 조이스틱 javascript 조이스틱javascript 프로그래머스

알고리즘 문제풀이 programmers Lv2

목록 보기

11/23

🕊 Link

Lv2. 조이스틱 Javascript
https://programmers.co.kr/learn/courses/30/lessons/42860#

🧑🏻‍💻 Code(javascript)

function solution(name) {
  let numA = "A".charCodeAt(); // 65
  let numZ = "Z".charCodeAt(); // 90
  const nums = [...name].map((item) => {
    const number = item.charCodeAt();
    return number - numA > numZ - number ? numZ - number + 1 : number - numA;
  });

  let result = nums.reduce((acc, cur) => acc + cur, 0);
  let index = 0;
  let len = nums.length;

  while (nums.some((el) => el !== 0)) {
    let next = 0;
    for (let i = 0; i < len; i++) {
      let right = (index + i) % len;
      let left = (index - i + len) % len;

      if (nums[right] !== 0) {
        next = right;
      } else if (nums[left] !== 0) {
        next = left;
      } else {
        continue;
      }
      nums[next] = 0;
      result += i;
      break;
    }
    index = next;
  }
  return result;
}

💡 Solution

그리디(탐욕) 알고리즘을 배경으로, 각각의 자리에서 최선의 방법을 찾는다.

1. 각 자리 조작 Count (▲▼)

A에서 오름차순으로 올라가는 것이 빠른지, Z에서 내림차순으로 내려가는 것이 빠른지 판단.
내려가는 경우에서는 A에서 Z로 넘어가는 count가 있기 때문에 +1
각 자리에서 조작해야하는 횟수를 nums 배열에 할당
nums의 모든 요소를 더해서 result에 할당(reduce)

2. 자리 이동 Count (◀▶)

while문, 모든 요소가 0이 될 때가지 Loop
for문으로 0~len까지 반복, next는 좌우로 몇칸을 움직일지 체크.
next오른쪽으로 갈 경우와 왼쪽으로 갈 경우의 인덱스를 계산 (for문이 아니라 %를 활용)
좌우 방향 확인
4-1. right가 0이 아닐 경우 ➤ next = right
4-2. right가 0이고, left가 0이 아닌 경우 ➤ next = left
4-3. right도 0이고, left도 0인 경우 ➤ continue : i++ 되면서, 좌우로 이동할 값이 올라감.
ex) 현재 index에서 좌로 1칸 / 우로 1칸을 확인하고 둘 다 0 인 경우, i++ ➤ 좌로 2칸 우로 2칸 확인 ...
right 혹은 left가 0가 아닌 경우 ➤ nums[next] = 0, result에 이동한 칸 i를 더하고 break
for문을 빠져나간 후 index를 next로 이동

💡 각 자리 조작 & 자리 이동
자리 이동을 하면서 각 자리에서 조작(▲▼)하는 횟수를 따로 더할 수도 있지만,
좌로가든 우로가든 각 자리에서의 조작의 합은 같으므로 먼저 result에 더해줌

💡 자리 이동 Count (◀▶) - 4번 과정
if : right, else if : left 순서
테스트 케이스 추가 : const name = "ZZAAAZZ" result = 8
right와 left가 동률일 경우, right로 가면 8이 나오지만, left로 가면 9가 나온다.
~~논란이 많은 문제~~