프로그래머스 - 조이스틱 (Java, 그리디)

아이디어

먼저 이 문제는

1. 알파벳을 업데이트 하는 것과
2. 이동하는 것

두 가지로 쪼갤 수 있다.

알파벳 업데이트

알파벳을 업데이트 하는 것은 단순히 A로부터 현재 알파벳에 도달하는 격차와,
Z로부터 현재 알파벳에 도달하는 격차 + 1 중 더 작은 것을 선택하면 된다.

 

이동

틀린 풀이

이동하는 것이 문제인데, 처음에는 잘못 생각해서 다음과 같이 풀이를 했었다.

1. 현재 위치를 0으로 잡고 왼쪽, 오른쪽 거리를 매긴다
2. 왼쪽에서 가장 가까운 Not A, 오른쪽에서 가장 가까운 Not A 간의 거리를 비교한다
3. 더 가까운 쪽을 선택하여 현재 위치를 업데이트하고, Not A인 알파벳의 갯수를 감소시킨다.

만약 Not A인 알파벳 갯수가 0이라면 종료. 종료 전까지 1 ~ 3 반복

나머지 예제는 전부 맞았지만, 예제 3번에서 오답이 나왔다.

"BBBBAAAABA"

이 같은 경우에 나의 초기 풀이대로 풀게 되면 13이 나오지만 정답은 12이다.
단순히 가까운 쪽을 그때 그때 선택하는 것보다, 왼쪽으로 갔다가 오른쪽으로 다시 돌아오는 쪽이 더 효율적인 경우이다.
위와 같이 A가 여러 개 뭉쳐있을 때는 초기 풀이를 적용할 수 없다.

 

 

맞는 풀이

현재 인덱스에서 A가 연속해서 있는 경우, 연속된 A가 끝나는 지점까지를 계산

1. 단순히 오른쪽으로 계속 이동하게 됐을 때 len - 1 번 이동 = 최댓값
2. 시작점에서 오른쪽으로 이동했다가 다시 왼쪽으로 가는 경우 = i * 2 + (len - endA)
3. 시작점에서 왼쪽으로 이동했다가 다시 오른쪽으로 가는 경우 = (len - endA) * 2 + i

 

3개 값 중 최소값이 이동 횟수가 된다.

import java.util.*;

class Solution {
    public int solution(String name) {
        int answer = 0, len = name.length(), move = len - 1;


        for(int i = 0; i < len; i++) {
            answer += Math.min(name.charAt(i) - 'A', Math.abs(name.charAt(i) - 'Z') + 1);

            if(i + 1 < len && name.charAt(i + 1) == 'A'){
                int endA = i + 1;
                while(endA < len && name.charAt(endA) == 'A') endA++;
                move = Math.min(move, Math.min(i * 2 + (len - endA), i + (len - endA) * 2));
            }

        }


        return answer + move;
    }
}