조이스틱 - 탐욕

 

주어진 이름을 조이스틱으로 완성할 때, 최소환의 조작 횟수를 구하는 문제이다. 이름을 완성하기 위해 필요한 최소한의 조작 횟수를 계산해야한다.

 

 

문제분석

각 문자를 'A'에서 목표 문자로 변경하기 위해 필요한 상/하 방향 조작 횟수를 계산한다.

 - 'A'에서 목표 문자를 만드는 두 가지 : 위로 이동 하거나 아래로 이동 

 - 예를 들어 'A에서 'B;로 변경하려면 위로 한번, 'A' 에서 'Z'로 변경하려면 아래로 한 번이다.

 

커서 이동 : 커서를 좌우로 움직여 각 문자를 완성 한다.

 - 왼쪽이나 오른쪽으로 이동할 때, 효율적인 경로를 선택해야한다. 모든 위치를 순차적으로 방문하는 것이 아닌, 'A'가 아닌 문자의 위치로 빠르게 이동해야한다.

 

class Solution {
    public int solution(String name) {
        int n = name.length();
        int answer = 0;
        int minMove = n - 1; // 기본적으로 모든 문자를 방문하는 경우의 커서 이동

        for (int i = 0; i < n; i++) {
            // 알파벳 변경 횟수
            char currentChar = name.charAt(i);
            int changeCount = Math.min(currentChar - 'A', 'Z' - currentChar + 1);
            answer += changeCount;

            // 커서 이동 최소값 계산
            int nextIndex = i + 1;
            while (nextIndex < n && name.charAt(nextIndex) == 'A') {
                nextIndex++;
            }

            // 현재 위치에서 이동해야 하는 경우와 뒤로 돌아서 이동하는 경우 중 최소값 선택
            int move = i + n - nextIndex + Math.min(i, n - nextIndex);
            minMove = Math.min(minMove, move);
        }

        answer += minMove;
        return answer;
    }
}

 

문자열의 각 위치에서 알파벳 변경과 커서 이동을 고려하여 문제에서 요구하는 최소 조작 횟수를 계산을 해야한다.

 

 

 

Script

이 문제에서 위 , 아래 그리고 좌, 우 로 이동이 가능할때 최소 조건으로 답을 구하는 문제이다. 그렇다면 우리가 생각해야하는건 현재 위치에서 이동할때 와 뒤로 돌아서 이동하는 경우 총 2가지를 생각하여 답을 구하는것이 가장 좋다. 

쉽게 생각하면 1 ~ 10 이 있으면 5라는 숫자에 도달하려면 앞으로 4번 이동하거나 뒤로 6번 이동해야한다. 이중 가장 적게 조작하여 도달할수 있는건 4번 이다. 이런 형식으로 생각하여 문제를 풀면 간단하다