[Java/자바] 프로그래머스 Lv2 - 조이스틱 (Greedy/탐욕법)

문제 설명

 

---

Solution.java

정답 코드

class Solution {
    public int solution(String name) {
        int answer = 0; // 조이스틱 조작 횟수
        int len = name.length();
        int move = name.length() - 1; // 기본 최소 좌우이동 횟수 (좌, 우 커서)
        
        // 해당 커서 알파벳 변경 최솟값 (위, 아래 커서)
        for (int i = 0; i < len; i++) {
            answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
            
            // 연속된 'A'가 끝나는 지점 찾기
            int next = i + 1;
            while(next < len && name.charAt(next) == 'A') {
                next++;
            }
            
            // 좌우이동 최소 횟수 구하기 (순서대로 가기 vs 뒤로 돌아가기)
            move = Math.min(move, (i * 2) + len - next);
            move = Math.min(move, (len - next) * 2 + i);
        }   
        answer += move;

        return answer;
    }
}

 

BBZAAAAC 의 경우 예시

1. 커서를 위 아래로 이동해 알파벳을 변경할 수 있는 최솟값들을 구합니다.

=> 커서를 위로 한 번 움직여 초기 알파벳 'A'를 B로 변경 : B 2개 - 총 2회

커서를 아래로 한 번 움직여 초기 알파벳 'A'를  Z로 변경 : Z 1개 - 총 1회

커서를 위로 두 번 움직여 초기 알파벳 'A'를  C로 변경 : C 1개 - 총 2회

 

2. 연속된 알파벳 'A'가 끝나는 지점의 인덱스 값을 찾습니다.

=> 2번째 인덱스의 Z에서 A가 아닌 알파벳 C가 있는 위치는 인덱스 7  

 

3. 좌우 이동 최소 횟수 구하기

(i * 2)는 B -> B -> Z 까지 움직인 다음에 다시 원점으로 Z -> B -> B 로 돌아가는 횟수입니다.

즉, (i * 2) + len - next 는 오른쪽으로 갔다가 왼쪽으로 움직여 'B'부터 'Z'까지 바꾸고 다시 시작점로 돌아 간후, 왼쪽으로 움직여 마지막 위치로 이동해서 'Z'로 바꾸는 경우이고,

(len - next) * 2 + i 는 시작점에서 왼쪽으로 움직여 마지막 위치에서 'C'로 바꾸고 다시 오른쪽으로 움직여 시작점으로 돌아와 'B'부터 'Z'까지 바꾸는 것입니다.