Today's Algorithm(2018-12-27)

programmers. 조이스틱

이번 문제를 풀면서 고민되었던 부분은 앞으로 진행하다가 다시 돌아서 뒤로 가는 경우였습니다. 예를들어 "JIAAAZ"의 경우 "JI"를 지나고 나서 그 사이 "AAA"을 지나가는 것보다 지났던 길을 다시 지나가더라도 되돌아가는게 더 효율적이기 때문입니다.

그래서 처음엔 이러한 경우를 위해서 dfs를 고려했습니다. 하지만 재귀로 호출되는 부분에서 어디서 어떻게 재귀적으로 호출하는지 저 스스로도 잘 몰라 에러가 발생하였고 더 문제인 것은 어디에서 에러가 발생했는지 모른다는 것이었습니다. 그 주된 이유가 dfs에서는 재귀적 호출을 계속 새로 만들고 또 새로 만들어진 것이 끝날 때까지 진행되는데 그 과정을 못 쫒았습니다.

그래서 뒤로 갈 수 있을 때 지금까지의 정보를 Job 이라는 객체에 넣어두고 그 객체를 Queue 에 담아 현재 진행하는 Job 이 끝난 이후에 실행되도록 하였습니다. 그렇게 하니 큰 혼란없이 끝낼 수 있었습니다. 이제 코드를 보도록 하겠습니다.

class Solution {
    public static final char A = 'A';

    public int solution(String name) {
        int answer = Integer.MAX_VALUE;
        StringBuilder targetText = new StringBuilder();
        for (int i = 0; i < name.length(); i++) {
            targetText.append(A);
        }
        String target = targetText.toString();

        Queue<Job> queue = new LinkedList<>();
        queue.offer(new Job(new StringBuilder(name), 1, 0, 0));

        while (!queue.isEmpty()) {
            Job job = queue.poll();

            while (!isSame(job.text, target)) {
                char data = job.text.charAt(job.curIndex);
                if (data != A) {
                    job.count += minChangeCount(data);
                    job.text.setCharAt(job.curIndex, A);
                }

                if (job.curIndex <= (job.text.length() - 1) / 2 - 1 && job.direction != -1) {  // 뒤로 가도 되는 시점들
                    int temp = (job.curIndex == 0 ? job.text.length() - 1 : job.curIndex - 1);  // index가 0보다 작을 때 처리
                    queue.add(new Job(new StringBuilder(job.text), -1, temp, job.count + 1));
                }

                if (!isSame(job.text, target)) {
                    job.count++;
                    if (job.curIndex == 0 && job.direction == -1) job.curIndex = job.text.length();  // index가 0보다 작을 때 처리
                    job.curIndex += job.direction;
                }
            }
            answer = Math.min(answer, job.count);
        }

        if (answer == Integer.MAX_VALUE) return 0;  // 이동거리가 없으면 0을 리턴

        return answer;

    }

    private int minChangeCount(char data) {  // 최소 거리
        return Math.min(data - A, 'Z' - data + 1);
    }

    private boolean isSame(StringBuilder text, String target) {
        return text.toString().equals(target);
    }
}

class Job {
    StringBuilder text;
    int direction;
    int curIndex;
    int count;

    public Job(StringBuilder text, int direction, int curIndex, int count) {
        this.text = text;
        this.direction = direction;
        this.curIndex = curIndex;
        this.count = count;
    }
}

코드는 보면 이해갈거라 생각합니다. 연산을 여러번 해야하고 그 안에서 최적의 값을 구해야할 때 위와 같이 하나의 객체를 만들어두고 Queue에 넣어둔 다음 해당 연산이 모두 끝나고 다시 꺼내 다시 연산하여 저희가 원하는 최적값을 결국 구할 수 있었는데요. 다음에도 써먹을만한 것 같아요!

 

수정)

이 글을 작성하고 이후 스터디를 통해서 테스트케이스에서 검증되지 못한 제 코드에서의 오류를 발견하게 되었습니다. 26째 줄인데요. 기존 코드는 처음부터 뒤로 가면 유리한 경우를 찾을 순 있지만 앞으로 갔다가 다시 뒤로 돌아갔을 때 유리한 시점을 찾는 것에선 answer에 1만큼 차이 나는 것을 발견할 수 있었습니다.

그 이유는 26줄에서 인덱스가 0이 아닐 때 job.curIndex 를 그대로 두어서 그렇습니다. 뒤에 queue에 넣을 때 job.count + 1 로 1을 증가시키는데 이 말은 하나가 이동한 걸로 친다는 것입니다. 하지만 job.curIndex 정보를 바로 큐에 넣는데 그렇다면 이동한 것이 반영이 안되기 때문입니다. 그렇기 때문에 이동되었다는 것과 큐에 넣은 시점 이후로 뒤로 간다는 점(job.direction = -1)을 고려하면 job.curIndex - 1로 수정하여야 합니다.