[프로그래머스] 조이스틱 (그리디)

문제 소개

 

오늘 풀었던 조이스틱 - 프로그래머스 문제를 정리합니다.
이 문제는 이름을 만들기 위해 조이스틱을 최소 몇 번 조작해야 하는지를 계산하는 문제입니다.
문제의 핵심은 "상하 이동(문자 변경)"과 "좌우 이동(커서 이동)"을 분리하여 최소 횟수를 각각 구하는 데 있습니다.

문제 링크: 조이스틱 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 알파벳을 변경하는 데 필요한 최소 상하 이동 횟수 계산
2. 커서를 이동할 때 A가 연속되는 구간을 고려하여 최소 좌우 이동 경로 탐색
3. 완성까지 필요한 총 이동 횟수 = 상하 + 좌우 합산

---

해결 과정 및 코드

핵심 아이디어

1. 각 알파벳은 'A'를 기준으로 ▲ 또는 ▼ 중 더 적은 횟수만큼 조작
   → 예: B는 ▲ 1번, Z는 ▼ 1번이 최적
2. 좌우 이동은 단순히 오른쪽 끝까지 가지 않고, 연속된 A 구간을 피하는 방향으로 왕복 전략 고려
   → 예: JAN에서는 A를 피하기 위해 왼쪽으로 회전하는 전략이 더 효율적
3. 연속된 A 구간을 찾아서 왼쪽·오른쪽을 각각 먼저 처리한 뒤 반대 방향으로 되돌아오는 최소 거리 계산

코드

시간 복잡도 : O(N)

class Solution {
    public int solution(String name) {
        int n = name.length();
        int answer = 0;
        
        // 1. 각 문자를 바꾸는데 필요한 최소 조작 횟수 계산
        for (int i = 0; i < n; i++) {
            char c = name.charAt(i);
            // 위로 이동 (A→B→C→...)
            int up = c - 'A';
            // 아래로 이동 (A→Z→Y→...)  
            int down = 'Z' - c + 1;
            answer += Math.min(up, down);
        }
        
        // 2. 좌우 이동의 최소값 구하기
        int minMove = n - 1; // 기본: 맨 끝까지 오른쪽으로 이동
        for (int i = 0; i < n; i++) {
            // 현재 위치에서 연속된 A의 끝 찾기
            int next = i + 1;
            while (next < n && name.charAt(next) == 'A') {
                next++;
            }
            
            // 전략 1: 오른쪽 i 먼저 처리 후 왼쪽 처리
            // 0 → i (오른쪽 이동) → 0 (되돌아옴(왼쪽이동)) → (n-1) → ... → next (왼쪽 이동)
            int case1 = i * 2 + (n - next);
            // 전략 2: 왼쪽 next 먼저 처리 후 오른쪽 처리  
            // 0 → (n-1) → ... → next (왼쪽 이동) → 0 (되돌아옴(오른쪽이동)) → i (오른쪽 이동)
            int case2 = (n - next) * 2 + i;
            
            minMove = Math.min(minMove, Math.min(case1, case2));
        }
        
        return answer + minMove;
    }
}