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

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

코딩테스트 연습 - 조이스틱

Greedy 알고리즘은 부분적인 최적해를 계속 확장 시켜서 전제적인 최적해를 찾는 알고리즘 입니다.

특정 위치에 도달해서 알파벳을 만들때 조이스틱을 몇번 위아래로 움직여야 하는지는 정해져 있습니다.

결정해야하는 부분은 오른쪽으로 가느냐 왼쪽으로 가느냐 입니다. 

이때 이미 알파벳이 완성된 부분으로 가는 것이 최적해를 찾는데 도움이 되지 않기 때문에,

조이스틱을 움직여야 하는 부분으로 커서를 움직이는 것이 좋습니다.

따라서 조이스틱을 많이 움직여야 하는곳으로 커서를 움직이는 것이 부분적으로 최적이다 라는 사실을 바탕으로 전체적인 최적해를 구할 수 있습니다. 

 

class Solution {
    public int calMinMoveCount(int answer, int curIdx, int[] alphabet) {
        answer += alphabet[curIdx];
        alphabet[curIdx] = 0;
        int left = 0;
        int right = 0;
        for (int i = 1; i < alphabet.length; i++) {
            right += (curIdx + i >= alphabet.length ? alphabet[curIdx + i - alphabet.length] : alphabet[curIdx + i]);
            left += (curIdx - i < 0 ? alphabet[curIdx - i + alphabet.length] : alphabet[curIdx - i]);
            if (left > right) {
                if (curIdx - 1 >= 0) {
                    return calMinMoveCount(++answer, curIdx - 1, alphabet);
                } else {
                    return calMinMoveCount(++answer, curIdx - 1 + alphabet.length, alphabet);
                }
            } else if (right > left || (right == left && right != 0)) {
                if (curIdx + 1 < alphabet.length) {
                    return calMinMoveCount(++answer, curIdx + 1, alphabet);
                } else {
                    return calMinMoveCount(++answer, curIdx + 1 - alphabet.length, alphabet);
                }
            }
        }
        return answer;
    }

    public int solution(String name) {
        int answer = 0;
        int A_POSITION = 65;
        char[] string = name.toCharArray();
        int[] moveStick = new int[string.length];

        for (int i = 0; i < string.length; i++) {
            int tmp = (int) string[i] - A_POSITION;
            moveStick[i] = Math.min(tmp, 26 - tmp);
        }

        answer = calMinMoveCount(answer, 0, moveStick);
        return answer;
    }
}