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

문제

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

프로그래머스

접근 방법 및 풀이

A를 원하는 알파벳으로 변경하는 방법은 A에서 B방향으로 변경하거나 반대방향인 Z로 방향으로 변경하는 두가지 방법중 조이스틱을 적게 사용하는 방향으로 변경

 

커서를 변경하는 방향은 왼쪽이나 오른쪽으로 변경하여 적게 움직이는 방향으로 변경을 하나, 여기서 중요한 점은 좌측 또는 우측으로 트리 그래프로 모든 경우의 수에서 가장 적게 움직이는 횟수를 구하여 반환해야 함

 

name이 "ABABAAAAAAABA"의 결과는 10

name이 "ABABAAAAAAAAAAAAABA"의 결과도 10

처음에 1번째 글짜를 B로 수정하러 가기 보다 0번째에서 왼쪽으로 두번 움직여 뒤에서 두번째 글자를 B로 수정하고 다시 오른쪽으로 3번 움직여 B로 수정하는 방법이 더 적은 조작으로 이름을 생성 할 수 있음

public class Q30_42860 {
    public int solution(String name) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < name.length(); i++) {
            sb.append("A");
        }

        Data data = new Data();
        data.input = sb.toString();

        Data leftData = left(name, data); // 처음의 시작을 왼쪽으로 이동
        Data rightData = right(name, data); // 처음의 시작을 오른쪽으로 이동

        return Math.min(leftData.count, rightData.count);
    }

    class Data {
        String input;
        int count;
        int index;

        public Data clone() {
            Data newData = new Data();
            newData.input = this.input;
            newData.count = this.count;
            newData.index = this.index;
            return newData;
        }
    }

    Data left(String name, Data beforeData) {
        if (name.equals(beforeData.input)) {
            return beforeData;
        }
        Data data = beforeData.clone();

        int length = name.length();

        char target = name.charAt(data.index);
        int gap = (int) target - (int) 'A';
        int count = Math.min(gap, 26 - gap);

        data.input = data.input.substring(0, data.index) + target + data.input.substring(data.index + 1, length);
        data.count += count;

        if (name.equals(data.input)) {
            return data;
        }

        int left = 0;
        int leftIndex = data.index;
        do {
            leftIndex--;
            left++;
            if (leftIndex == -1) {
                leftIndex = length - 1;
            }
        } while (name.charAt(leftIndex) == data.input.charAt(leftIndex) && leftIndex != data.index);
        data.count += left;
        data.index = leftIndex;

        Data leftData = left(name, data);
        Data rightData = right(name, data);
        if (leftData.count < rightData.count) {
            return leftData;
        } else {
            return rightData;
        }
    }

    Data right(String name, Data beforeData) {
        if (name.equals(beforeData.input)) {
            return beforeData;
        }
        Data data = beforeData.clone();

        int length = name.length();

        char target = name.charAt(data.index);
        int gap = (int) target - (int) 'A';
        int count = Math.min(gap, 26 - gap);

        data.input = data.input.substring(0, data.index) + target + data.input.substring(data.index + 1, length);
        data.count += count;

        if (name.equals(data.input)) {
            return data;
        }

        int right = 0;
        int rightIndex = data.index;
        do {
            rightIndex++;
            right++;
            if (rightIndex == length) {
                rightIndex = 0;
            }
        } while (name.charAt(rightIndex) == data.input.charAt(rightIndex) && rightIndex != data.index);
        data.count += right;
        data.index = rightIndex;

        Data leftData = left(name, data);
        Data rightData = right(name, data);
        if (leftData.count < rightData.count) {
            return leftData;
        } else {
            return rightData;
        }
    }
}