17. 프로그래머스 - 조이스틱 (그리디)

문제 설명

조이스틱을 사용해 주어진 이름을 완성해야 합니다.
처음에는 모든 문자가 'A'로 채워져 있습니다.
예를 들어, 이름이 세 글자면 "AAA", 네 글자면 "AAAA"로 시작합니다.

조이스틱 조작 방식은 다음과 같습니다:

• 위 방향(▲) : 현재 문자를 다음 알파벳으로 변경 (예: A → B → C → ... → Z)
• 아래 방향(▼) : 현재 문자를 이전 알파벳으로 변경 (예: A ↓ → Z)
• 오른쪽(▶) : 커서를 오른쪽으로 이동 (마지막 문자일 경우 첫 문자로)
• 왼쪽(◀) : 커서를 왼쪽으로 이동 (첫 문자일 경우 마지막 문자로)

---

예시 설명

이름 "JAZ"를 만드는 경우:

1. 첫 번째 문자 'A'를 'J'로 만들기 위해 ▲ 9번
2. 커서를 왼쪽으로 1번 이동 (첫 위치에서 왼쪽 → 마지막 위치로 이동)
3. 마지막 위치 'A'를 'Z'로 만들기 위해 ▼ 1번

총 11번 조작으로 "JAZ" 완성 → 최솟값

---

입력

• 문자열 name (길이: 1 이상 20 이하)
• name은 알파벳 대문자로만 구성

---

출력

• name을 완성하기 위한 조이스틱 조작 횟수의 최소값을 반환

---

입출력 예시

name	return
"JEROEN"	56
"JAN"	23

---

 

문제 핵심

 

• 알파벳 변경 횟수 계산 (위/아래)
• 커서 이동 횟수 계산 (왼쪽/오른쪽, A 회피 포함)

단순히 오른쪽으로 커서를 이동하는 경우와 연속된 A를 우회하거나 되돌아가서 더 빨리 끝낼 수 있는 경우를 비교해서 낮은 쪽을 선택하는 것이 핵심이라고 할 수 있다.

 

알고리즘 코드

class Solution {
    public int solution(String name) {
        int answer = 0;
        int length = name.length();
        int move = length - 1;
        
        for(int i = 0; i < length; i++) {
            char c = name.charAt(i);
            answer += Math.min(c - 'A', 'Z' - c + 1);
            
            int next = i + 1;
            while(next < length && name.charAt(next) == 'A') {
                next++;
            }
            
            move = Math.min(move, i + length - next + Math.min(i, length - next));
        }
        
        return answer + move;
    }
}

 

 

그 후 알파벳 변경 횟수와 커서 이동 횟수를 더해주면 되는 문제다.

 

시간 복잡도 분석

알파벳 조작 계산: O(N)  
커서 이동 계산:    O(N)
= 전체 시간 복잡도: O(N)