[프로그래머스] 조이스틱

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

프로그래머스

• 각 자리의 알파벳을 바꾸는 횟수와 자리를 이동하는 횟수를 더하면 된다. 
• 각 자리의 알파벳을 바꾸는 횟수는 간단하다.

answer += Math.min(name.charAt(i) - 'A', 26 - (name.charAt(i) - 'A'));

• 자리를 이동하는 횟수를 구하는게 어렵다. 자리를 이동하는 방법은 다음과 같이 3가지가 있다.
  1. 쭉 오른쪽으로 이동
  2. 먼저 오른쪽으로 가다가 왼쪽으로 이동
  3. 먼저 왼쪽으로 가다가 오른쪽으로 이동
• 연속된 A의 시작과 끝 위치를 찾고, 끝나는 다음 위치인 endA를 찾는다. (ex, BCAAC인 경우 endA는 인덱스 4)
• 첫 시작 위치는 인덱스 0이다. 
  • 따라서 먼저 오른쪽으로 가다가 왼쪽으로 이동하는 횟수는 i * 2 + name.length() - endA 이다.
  • 그리고 먼저 왼쪽으로 가다가 오른쪽으로 이동하는 횟수는 (name.length() - endA) * 2 + i 이다.
• 따라서 i = (0 ~ name.length() - 1)의 범위로 for문을 돌면서, 움직이는 횟수를 계속해서 최솟값으로 갱신하면 된다. 
• BAZAA와 같이 연속된 A가 한 번 나오는게 아니라 여러 번 나올 수 있는데, 이 경우에도 위 알고리즘이 정상적으로 적용되는지가 궁금했다. 그런데, for문을 돌면서 moveCount 값을 계속해서 최솟값으로 갱신하므로 괜찮다! 
  • 쭉 오른쪽으로 이동: 4
  • i = 0, endA = 2
    • 먼저 오른쪽으로 가다가 왼쪽으로 이동: B, A, A, Z = 3
    • 먼저 왼쪽으로 가다가 오른쪽으로 이동: B, A, A, Z, A, A, B = 6
  • i = 2, endA = 5
    • 먼저 오른쪽으로 가다가 왼쪽으로 이동: B, A, Z, A, B = 4
    • 먼저 왼쪽으로 가다가 오른쪽으로 이동: B, A, Z = 2
  • i = 3, endA = 5
    • 먼저 오른쪽으로 가다가 왼쪽으로 이동: B, A, Z, A, Z, A, B = 6
    • 먼저 왼쪽으로 가다가 오른쪽으로 이동: B, A, Z, A = 3
  • 따라서 최소 moveCount = 2

// 시간 복잡도: O(N)
class Solution {

    public int solution(String name) {

        int answer = 0;
        int moveCount = name.length() - 1; // 오른쪽으로 쭉 간 횟수

        for (int i = 0; i < name.length(); i++) {
            answer += Math.min(name.charAt(i) - 'A', 26 - (name.charAt(i) - 'A'));
            if (i < name.length() - 1 && name.charAt(i + 1) == 'A') {
                int endA = i + 1;
                while (endA < name.length() && name.charAt(endA) == 'A') {
                    endA++;
                }
                // endA: 연속된 A가 끝난 다음 인덱스
                moveCount = Math.min(moveCount, i * 2 + (name.length() - endA)); // 오른쪽으로 갔다가 왼쪽으로 간 횟수
                moveCount = Math.min(moveCount, (name.length() - endA) * 2 + i); // 왼쪽으로 갔다가 오른쪽으로 간 횟수
            }
        }
        return answer + moveCount;
    }
}