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

• 문제

• 이 풀이 및 코드는 2022년 3월 14일 재검토 시점에 오답으로 처리되고 있습니다.

풀이과정

1. 주어진 문자열의 현재 위치(시작시 0)에서 가장 가까운 ‘A’가 아닌 문자의 위치를 찾는다.
2. 해당 위치까지 이동할 때, 좌우 방향 중 더 적은 이동횟수를 센다.
3. 해당 문자를 ‘A’로 바꾸기 위해 상하 방향 조작 횟수를 센다.
4. 2와 3의 결과를 더한다. 해당 문자를 ‘A’로 교체한다.
5. 더이상 ‘A’ 문자가 없을 때 까지 1~4 과정을 반복한다.

위 과정처럼 문제를 풀이했을 때 테스트 케이스 11, 13, 23, 25, 26에서 실패가 발생한다.

• 이에, 위 과정 중 2번 과정에서 좌우 방향 이동횟수가 같을 때 어느 한 쪽 방향에 대한 우선도가 존재하는지 확인 해 보았으나 별도의 우선도가 존재하지는 않는 것으로 보인다.
• 그 외에도, 좌측의 변환 필요 글자가 더 가까움에도 우측으로 먼저 이동해야 하는 경우 또는 그 반대의 경우도 존재하는 것으로 보인다.

Greedy 알고리즘의 핵심은 당장 눈 앞의 최적해들의 집합이 전체의 최적해(또는 그것에 매우 가까운 해)가 될 것으로 기대하는 것이라고 생각한다. 하지만 위와 같은 경우 (예를들어 ”BBBBAAAAAB” 등) 당장 눈 앞의 최적해를 선택하면 전체의 최적해를 찾을 수 없는 문제가 발생한다. 이는 현실의 문제에서라면 충분히 발생 가능한(오히려 더 많이 발생할 수도 있는) 경우이겠지만, Greedy 알고리즘 문제에는 적절하지 않아 보인다.


문제의 공지사항에서 2022년 1월 14일에 지문 수정 및 테스트케이스의 추가가 이루어 졌다고 했는데, 이 과정에서 Greedy 알고리즘 문제에 알맞지 않은 테스트 케이스가 추가된 것은 아닌가 의심스럽다. 일단 현재는 오답인 상태로 잠시 그대로 두고, 추후 문제의 수정이 없을 시 Brute Force 방식으로 다시 풀이를 해야 할 것으로 보인다.

Code

package greedy;

public class JoyStrick {
    public int currentIndex = 0;

    public int solution(String name) {
        currentIndex = 0;
        // 역으로 주어진 name을 "AAA...A"로 바꿔 나가며 필요한 조작 횟수를 센다.
        int count = 0;
        char[] chars = name.toCharArray();

        int targetIndex = findTargetIndex(chars, currentIndex);
        while (targetIndex != -1) {
            count += horizontalHandlingCount(chars, targetIndex);
            count += verticalHandlingCount(chars[currentIndex]);
            chars[currentIndex] = 'A';

            targetIndex = findTargetIndex(chars, currentIndex);
        }

        return count;
    }

    private int verticalHandlingCount(char targetChar) {
        return Math.min(targetChar - 'A', 'Z' - targetChar + 1);
    }

    private int horizontalHandlingCount(char[] chars, int targetIndex) {
        int moveCountRight = countRightMoving(targetIndex, chars.length);
        int moveCountLeft = countLeftMoving(targetIndex, chars.length);

        // 좌우방향으로 이동했음을 가정
        this.currentIndex = targetIndex;

        return Math.min(moveCountRight, moveCountLeft);
    }

    private int findTargetIndex(char[] chars, int currentIndex) {
        for (int moveCount = 0; moveCount <= chars.length / 2; moveCount++) {
            int leftTargetIndex = (currentIndex - moveCount) < 0 ? currentIndex - moveCount + chars.length : currentIndex - moveCount;
            if (chars[leftTargetIndex] != 'A') {
                return leftTargetIndex;
            }

            int rightTargetIndex = (currentIndex + moveCount) % chars.length;
            if (chars[rightTargetIndex] != 'A') {
                return rightTargetIndex;
            }
        }

        return -1;
    }

    private int countRightMoving(int targetIndex, int stringLength) {
        int currentIndex = this.currentIndex;
        int count = 0;

        while (currentIndex != targetIndex) {
            currentIndex = (currentIndex + 1) % stringLength;
            count++;
        }

        return count;
    }

    private int countLeftMoving(int targetIndex, int stringLength) {
        int currentIndex = this.currentIndex;
        int count = 0;

        while (currentIndex != targetIndex) {
            currentIndex = currentIndex < 1 ? stringLength - 1 : currentIndex - 1;
            count++;
        }

        return count;
    }
}

결과