조이스틱

YEONGHUN KO·2021년 12월 9일
0

ALGORITHMS - PRACTICE

목록 보기
34/50
post-thumbnail

1. 조이스틱

이 문제는 살짝 복잡할 수 도 있다. 그래서 타인의 코드를 참고하였는데 오류가 발생해서 내 나름의 방법을 적용해서 해결했다!!! 대박이다...!

문제설명: 조이스틱을 위아래로 움직이면 알파벳이 바뀌고 양옆으로 움직이면 위치가 변경가능하다고 하자. 이때 주어진 알파벳으로 이름을 바꾼다고 할때 최소 움직여야할 조이스틱의 횟수를 구하면 된다. (모든 이름의 초기값은 A이다.)

예를 들어, JAN와 같은 이름이 주어졌다고 했을 때 AAA에서 JAN으로 조이스틱을 움직여서 바꾸어야 한다. A에서 J로 바꾸고 커서의 위치를 옮겨서 마지막 A를 N으로 바꾸면 된다.

2. 접근 방법

우선 알파벳을 바꾼다고 할때 A에서 쭉 전진해야할지 아님 Z에서 거꾸로 시작해야할지를 선택해야한다. 계산해보니깐 N을 기준으로 A와 가까이 있는 것은 그대로 Z와 가까이 있는것은 거꾸로 가면 된다.

커서의 이동방향도 고려해야한다. 오른쪽으로 이동할 것인지 왼쪽으로 , 거꾸로 이동할 것인지.

사실 내가 나름대로 짠 코드로 이 글을 정리하려 했으나, 예외상황이 많이 발생하였고 그 예외상황을 고려해서 코드를 짜볼려고 했지만 더더욱 복잡해지기만 했다. 다행이도 좋은 코드를 발견했고, 한큐에 정리가 되면서 글을 끝낼 수 있게 되었다.

일단 , 다음과 같이 3가지 이름이 주어졌다고 하자.

  1. ACSERAAAAAA

  2. ACSDFAAAASO

  3. SEFWVAARAAAA

1번은 오른쪽으로 R까지만 가면 된다.

2번같은 경우는 왼쪽으로 이동해서 오른쪽 글자를 왕복한다음 다시 돌아와서 왼쪽의 글자를 순회한다.

3번도 마찬가지로 오른쪽으로 R까지만 이동하면 된다.

그럼 코드로는 어떻게 나타낼 것인가?

  • pseudo code

  • charCodeAt을 이용해서 각알파벳을 변환할때 필요한 움직임 횟수를 더함

  • 왼쪽, 오른쪽으로 움직이는 커서의 움직임 횟수를 구함

    • 연속으로 이루어진 A를 기준으로 해서 왼쪽에 있는 글자가 많은지 오른쪽에 있는 글자가 많은지 비교한다음 적은 글자쪽으로 왕복한다음 글자가 많은 쪽으로 돌아와서 많은 쪽 글자들을 순회하면 된다.

    • 그렇게 순회가 끝나면 움직인 횟수를 minMove에 담는다. 그리고 또 다시 연속된 A가 나오면 움직인 횟수를 계산한다음 기존의 minMove와 비교해서 더 적은쪽이 minMove가 된다.

      • 3번같은 경우는 연속된 A가 두번 나오므로 비교를 2번해야한다.(왕복보다는 R쪽으로 쭉 이동하는게 더 적게 걸리기 때문에 그렇게 나올것이다.)
function solution(name) {
  let sum = 0;

  const changeAlphabet = (letterNum) =>
    // Z(91) 에서 letterNum을 빼느냐 아님 letterNum에서 A(65)를 빼느냐
    letterNum > 78 ? 91 - letterNum : letterNum - 65;

  for (let i = 0; i < name.length; i++)
    sum += changeAlphabet(name.charCodeAt(i));

  let minMove = name.length - 1;

  for (let i = 1; i < name.length; i++) {
    // A일때만 모든것이 움직인다.
    //일단 가까운 'A'의 인댁스 i 를 찾는다.
    if (name[i] === "A") {
      for (let j = i + 1; j < name.length; j++) {
        // i로부터 가장가까운 'A'가 아닌값 인댁스 j를 찾는다.
        if (name[j] !== "A") {
          break;
        }
      }

      // 여기까지 오면 가까운 'A'의 인댁스i 와, i다음 인댁스부터 'A'가아닌 인댁스 j 가 저장되어있다.
      // (이 사이의 인댁스는 무조건 A로, 도달하지 않아도 되는값 )
      // 그럼 나머지를 순회하는방법은 4가지가 있는데,
      // 왼쪽으로 가거나, 오른쪽으로 가거나,
      // 왼쪽으로가다가 오른쪽으로가거나, 오른쪽으로 가다가 왼쪽으로 가는경우이다.
      // 어떤게 효율적인지 알기위해서

      const left = i - 1; //i,j범위밖의 왼쪽 거리를 재고,
      const right = name.length - j; // i,j 범위밖의 오른쪽 거리를 잰다.

      // 이때 둘중 하나가 0이라면, 오른쪽 혹은 왼쪽으로만 가는 경우이고

      // 둘다 값이 있다면 한쪽으로가다가 반대쪽으로 돌아가는 경우인데

      // 돌아가는경우엔 길이에 *2를 해줘야 총 움직이는 시간이 된다.
      // 최소값을 구해야 하므로 left나 right 중에 '작은값에' *2 를 해준다.

      // 예를 들어서 'ACSERAAAAAA' 라고 하면 i = 5 , j = name의 길이. 가 된다. A의 시작과 끝을 나타내는 것이다.
      // 따라서, left= 4, right = 0 이 된다. 이때 오른쪽이 더 적으므로 오른쪽에서 움직여야하는 거리를 왕복한다음에 왼쪽거리를 더하면 된다.
      // 근데 여기서는 오른쪽 에 왕복할 알바벳이 없으므로 바로 왼쪽으로 넘어와서 왼쪽거리를 더한다

      // 만약에 'ACSAAAASDFO' 라고 한다면 A를 기준으로 왼쪽에는 글자 2개 오른쪽은 4개있다.
      // 따라서 왼쪽왕복하고 오른쪽으로 넘어와서 4를 더해주면 최소 움직인 횟수가 나오는 것이다!

      minMove = Math.min(
        minMove,
        left > right ? right * 2 + left : left * 2 + right
      );

      i = j; // i,와 j 사이의 값은 무조건 A 로 탐색할 필요가 없으니 i를 j로 업데이트 해준다. 루프가지나면 i=j+1이 된다.
    }
  }

  return sum + minMove;
}

항상 느끼는 거지만 좋은 코드를 짜는 사람이 있어서 감사하고 그걸 내가 아무대가없이 배울 수 있게 되어서 감사하다. 나도 꼭 나중에 실력이 좋아지면 내 능력을 베푸는 사람이 될거다!!

profile
'과연 이게 최선일까?' 끊임없이 생각하기

0개의 댓글