[프로그래머스/알고리즘 고득점 Kit] 탐욕법(Greedy) - 조이스틱 (Java)

조이스틱

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

---

풀이

알파벳 변경

처음 알파벳 A에서 위로 가는 횟수 vs 아래로 가는 횟수 -> 더 작은 값

for (int i = 0; i < n; i++) {
    char c = name.charAt(i);
    cnt += Math.min(c - 'A', 'Z' - c + 1);
}

 

커서 이동

문자 길이 n -> 기본 이동(`move`): n - 1

• 중간에 A 없음 -> 그냥 오른쪽으로 커서 이동
• 중간에 A 있음 -> 돌아가는 게 나을 수도 있음
  • ex. JAN
    • 오른쪽으로만 이동: 0 -> 1 -> 2 => 2칸
    • 뒤로 돌아서 이동: 0 -> 왼쪽 -> 2 => 1칸

 

• 오른쪽 갔다가 돌아오기: `i * 2 + (n - next)`
  • 오른쪽: i / 되돌아오기: i / 왼쪽으로 끝까지: n - next
• 왼쪽 갔다가 돌아오기: `(n - next) * 2 + i`
  • 왼쪽: n - next / 되돌아오기: n - next / 오른쪽: i

int move = n - 1;
for (int i = 0; i < n; i++) {
    int next = i + 1;
    while (next < n && name.charAt(next) == 'A') next++;

    move = Math.min(move, i * 2 + (n - next));
    move = Math.min(move, (n - next) * 2 + i);
}

---

코드

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