프로그래머스[Level 2] 조이스틱 (그리디) x

문제

제한 사항

입출력 예

풀이

function count(n) {
  let cnt = 0;
  if (n < 78) {
    cnt += n % 65;
  } else {
    cnt += 91 - n;
  }
  return cnt;
}
const solution = (name) => {
  let answer = 0;
  let min = name.length - 1; // 커서를 최대로 이동해도 문자열의 길이 -1을 넘지 않을 것임.

  for (let i = 0; i < name.length; i++) {
    let cur = name.charCodeAt(i);

    answer += count(cur);

    // 커서 이동 신경써주는 코드
    let nextIndex = i + 1; // 다음 인덱스
    while (nextIndex < name.length && name.charCodeAt(nextIndex) === 65) {
      nextIndex++;
    } // 다음 문자가 a이면 계속 옆으로 이동해준다. 마지막 a의 다음 인덱스에서 멈춘다.

    min = Math.min(min, i * 2 + name.length - nextIndex);
    // i*2는 현재 커서에서 되돌아가는 경우,
    // name.length - nextIndex A가 아닌 문자로 커서를 옮기는데 반대로 이동하는 수
    min = Math.min(min, (name.length - nextIndex) * 2 + i);
    // 뒷 부분이 짧은 경우(BBBBAAAAAAAB 와 같이) 뒷부분을 먼저 바꾸고 i위치로 가는 케이스
  }
  answer += min;
  return answer;
};

• 그리디라고 하기엔 애매한 것 같다.
• 오락실 게임에서 순위를 갱신하면 이름을 남기는 것과 같게 생각하면 된다.
• count 함수는 알파벳을 A에서 얼마나 이동시켜주는지 세어주는 함수이다. 조건문의 기준인 78은 알파벳 중 가운데인 N의 아스키 코드 값이다.
• 이 문제의 어려운 점은 커서를 이동할 최소 값을 찾는 방법이다. 반복문을 통해 nextIndex의 값은 연속되는 A를 모두 지나친 A가 아닌 알파벳의 인덱스 값이다. 연속된 A의 수가 많아서 뒤에서부터 이동하는 케이스가 최소 값이 될 수 있기 때문에 i * 2 + name.length - nextIndex 형태가 나온 것인데 자세한 것은 주석을 살펴보자.
• 아예 뒤에를 먼저 바꾸고 오는게 짧을 수도 있기 때문에 (name.length - nextIndex) * 2 + i 도 비교 대상이 된다.

다른 코드

// 알파벳의 이동의 수를 세어주는 함수
function count(n) {
  let cnt = 0;
  if (n < 78) {
    cnt += n % 65;
  } else {
    cnt += 91 - n;
  }
  return cnt;
}

function solution(name) {
  let answer = 0;
  let cursorCountList = [name.length - 1];
  for (let i = 0; i < name.length; i++) {
    answer += count(name.charCodeAt(i));
  }

  for (let j = 0; j < name.length; j++) {
    let endOfA = j + 1;
    while (endOfA < name.length && name[endOfA] === "A") {
      endOfA++; // 마지막 A 다음 알파벳의 INDEX
    }
    cursorCountList.push(j * 2 + name.length - endOfA); // 오른쪽으로 이동하다 처음으로 다시 돌아가는 경우
    cursorCountList.push((name.length - endOfA) * 2 + j); // 시작부터 뒤로 가는 경우
  }
  answer += Math.min(...cursorCountList);
  return answer;
}

• 같은 원리이다.