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

문제 링크

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

문제 설명

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

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

 

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

 

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

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

 

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한 사항

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

 

내 풀이

이 문제는 탐욕법 문제로, 두 가지 문제가 동시에 존재합니다.

1. 상하로 움직여서 알파벳을 변경하기
2. 좌우 커서 이동 수

1. 상하로 움직여서 알파벳을 변경하기

function changeAlphabet(name) {
    const alphabet = ['A','B','C','D','E','F','G','H','I','J','K',"L","M",'N','O','P','Q','R','S','T','U','V','W','X','Y','Z'];
    let result = 0;
    for (let i = 0; i < name.length; i++) {
        if (alphabet.indexOf(name[i]) > 13) {
            result += 26 - alphabet.indexOf(name[i])
        } else {
            result += alphabet.indexOf(name[i])
        }
    }
    return result;
}

단순하게 배열을 만들고, 인덱스가 중간값인 13보다 크다면, 하 버튼을 눌러 버튼수를 최소화하였습니다.

만약 인덱스가 중간값보다 작다면 상 버튼을 누르는 형태로 구성했습니다.

2. 좌우 커서 이동 수

다양한 케이스들을 보겠습니다.

 

1. 순서대로 이동하는 경우

모든 글자를 변경해야 하는 경우, 오른쪽으로 진행하거나 왼쪽으로 진행하는 경우 모두가 같습니다.

그러므로 단순하게 오른쪽으로 계속 이동했을때의 값을 넣어주면 됩니다.

 

2. 오른쪽으로 갔다가 왼쪽으로 방향을 변경하는 경우

중간에 A가 다수 있는 경우, 단순하게 오른쪽으로 더 많이 가는 경우 조이스틱의 횟수가 더 많이 증가하게 됩니다.

• 단순하게 오른쪽으로 이동한 경우 : 11
• 오른쪽으로 갔다가 왼쪽으로 이동하는 경우 : 1 + 1 + 3 = 5

이런 경우에는 오른쪽으로 갔다가 왼쪽으로 이동하는 경우가 더 적게 움직입니다.

 

3. 왼쪽으로 갔다가 오른쪽으로 방향을 변경하는 경우

 

마찬가지로 A가 다수 있는 경우를 생각해보겠습니다.

이번에는 2,3,4에 B가 존재하고, 맨 마지막에 B가 존재합니다.

이러한 경우에는 

1. 왼쪽으로 한칸 이동해서 B를 먼저 변경한다.
2. 오른쪽으로 한칸 이동해서 원래 자리로 돌아온다.
3. 다시 오른쪽으로 이동하면서 변경한다.

이 경우를 계산해보자면

• 단순하게 오른쪽으로 이동한 경우 : 12
• 오른쪽으로 갔다가 왼쪽으로 이동한 경우 : 3 + 3 + 1 = 7
• 왼쪽으로 갔다가 다시 오른쪽으로 이동 : 1 + 1 + 3 = 5

이러한 경우에는 왼쪽으로 갔다가 오른쪽으로 이동하는 경우가 더 적게 움직입니다.

 

이것을 코드로 적용시켜보겠습니다.

function moveHorizontal(name) {
	// move는 기존 값을 우로 계속 이동하는 값을 넣어줍니다.
    // 만약 다른 작은 값이 나왔다면 해당하는 값을 넣어줄 수 있도록 let으로 지정합니다.
    let move = name.length - 1; 
    
    let index; // 다음 값들이 A인지 확인하기 위해 사용
    for (let i = 0; i < name.length; i++) {
        index = i + 1;
        // 연속되는 A 갯수 확인하기
        while(index < name.length && name[index] == 'A') {
            index++;
        }
        // 기존값과, 뒤로 돌아가는 것 중 이동수가 적은 것을 선택합니다. (i * 2) + (name.length - index)
        // 처음부터 뒷부분을 먼저 입력하는 것이 더 빠른 경우까지 추가하였습니다. (name.length - index) * 2 + i)
        move = Math.min(move, (i * 2) + (name.length - index), (name.length - index) * 2 + i);
    }
    return move;
}

다른 사람의 풀이

다른 사람이 조금 더 간단하게 풀었지만, 이 문제는 탐욕법이므로 저는 구분하여 풀었습니다.

function solution(name) {
    let sum = 0;
    for (let i = 0; i < name.length; i++) {
        let diff = name[i].charCodeAt() - 'A'.charCodeAt();
        sum += diff > 13 ? 26 - diff : diff;
    }

    let minMove = name.length - 1;
    for (let i = 1; i < name.length; i++) {
        if (name[i] === 'A') {
            for (var j = i + 1; j < name.length; j++) {
                if (name[j] !== 'A') {
                    break;
                }
            }

            const left = i - 1;
            const right = name.length - j;
            minMove = Math.min(minMove, left > right ? left + right * 2 : left * 2 + right);

            i = j;
        }
    }

    return sum + minMove;
}

오늘 배운 점

처음 문제를 풀 때, 좌우 이동하는 것을 단순하게 좌로 이동하거나, 우로 이동하는줄만 되는 줄 알고 코드를 이렇게 작성하였습니다.

function moveHorizontal(name) {
  const isA = (value) => value == "A";
  const nameArr = name.split("");
  // nameArr을 바로 reverse 돌리면 같은 주소값을 사용하기 때문에 에러 발생
  const reverseArr = name.split("").reverse();
  console.log(reverseArr);
  let left = 0;
  for (let i = 0; i < name.length; i++) {
    // 1. 인덱스에 해당하는 값을 변경
    nameArr[i] = "A";
    // 2. 더이상 변경해야 하는지 확인
    if (nameArr.every(isA)) {
      break;
    }
    // 3. 또 변경해야 된다면 넘어간다.
    left++;
  }
  // 오른쪽은 첫번째 글자를 이미 변경한 상태.
  // 따라서 초기 값을 1로 시작하고, 가장 첫번째 인덱스 값을 A로 변경
  let right = 1;
  reverseArr[name.length - 1] = "A";

  for (let j = 0; j < name.length - 1; j++) {
    reverseArr[j] = "A";
    if (reverseArr.every(isA)) {
      break;
    }
    right++;
  }

  if (left <= right) {
    return left;
  } else {
    return right;
  }
}

 

그러나 몇몇 테스트가 통과하지 못했고, 잠시 생각해 봤을 때 중간에서 뒤돌아가거나, 아니면 처음부터 마지막을 변경한 다음 앞으로 돌아오는 방법도 존재하였습니다.

 

코딩 테스트를 풀 때 조금 더 경우의 수를 생각하고 풀어야겠다는 생각을 하게 되었습니다.

또한 Array.every() 메서드를 알게 되었습니다.

Array 인스턴스의 every() 메서드는 배열의 모든 요소가 제공된 함수로 구현된 테스트를 통과하는지 테스트합니다. 이 메서드는 불리언 값을 반환합니다.

const isBelowThreshold = (currentValue) => currentValue < 40;

const array1 = [1, 30, 39, 29, 10, 13];

console.log(array1.every(isBelowThreshold));
// Expected output: true

참고

Array.prototype.every() - JavaScript | MDN

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