[JS] 조이스틱

🔒 문제 (프로그래머스 - 그리디 알고리즘)

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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) 상하 커서 조작

아스키코드를 이용하여 각 알파벳이 A에서 얼만큼 떨어져 있는지 계산 =>  charCodeAt() (A : 65, Z: 90)

알파벳 개수는 26, 그 절반은 13. 현재 알파벳이 A로부터 떨어진 거리가 절반을 넘지 않을 경우 

이동 횟수 = (현재 알파벳의 아스키코드 값) % (A의 아스키코드 값)

절반을 넘어갈 경우 A → Z 방향으로 조작하며

이 때 이동 횟수 = (Z의 아스키코드 값) - (현재 알파벳의 아스키코드 값) + 1

2) 좌우 커서 조작

문자열에서 연속된 A의 개수를 세어 그 부분을 (A1....An) 이라고 하면

i) 오른쪽으로 이동하다가 A1을 만났을 때 왼쪽으로 이동 vs ii) 왼쪽으로 이동하다가 An을 만났을 때 오른쪽으로 이동

하는 경우 조작 횟수를 계산하여 중 작은 것을 선택한다.

i) 조작 횟수 = (A1까지 이동 횟수 X 2) + (A1에서 name의 끝을 거쳐 An 까지 이동한 횟수)

ii) 조작횟수 = (An에서 name의 끝 알파벳까지 이동한 횟수) + (name의 끝에서 처음을 거쳐 A1 까지 이동한 횟수)

function solution(name) {
    let answer = 0;
    let minArr = [name.length - 1];
  
    for(let i = 0; i < name.length; i++) {
        let ascii = name.charCodeAt(i);
        
        // 상하 조작 횟수 계산
        if(ascii < 78) {
            answer += ascii % 65;
        } else {
            answer += 91 - ascii;
        }
        
        // 좌우 조작 횟수 계산
        let nextIndex = i + 1;
        while(nextIndex < name.length && name.charCodeAt(nextIndex) === 65) {
            nextIndex++;
        }
        const moveToEndOfA = name.length - nextIndex;
        const moveToStartOfA = i; 
        minArr.push(moveToStartOfA * 2 + moveToEndOfA);
        minArr.push(moveToEndOfA * 2 + moveToStartOfA);
    }
    
    answer += Math.min(...minArr);
    return answer;
}