[PGM_42860] 조이스틱 (java)

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 브루트포스

1. 문제 이해

입력으로 알파벳으로 이루어진 문자가 주어지면, 조이스틱을 움직여 그 문자를 만들 때 최소한으로 조이스틱을 움직이는 경우를 구하는 문제이다. 조이스틱은 위,아래 그리고 좌,우로 움직일 수 있으며 위와 아래로 움직이는 경우 알파벳이 변경되고 좌우로 움직이면 해당 문자의 위치가 변경된다.

 

초기 문자는 A로 이루어져있으며 A부터 Z까지 대문자로만 이루어져있다.

 

2. 접근방법

좌우로 움직이는 방법과 위 아래로 움직이는 방법 이 두 가지를 나누어 생각해주었다.

 

- 위 아래로 움직이는 경우

위 아래로 움직이는 경우는 문자를 변경해주는 경우이다. 문자는 A 부터  Z까지 순서대로 움직이게 된다. 이 때 최소가 되기 위해서는 위로만 계속 움직이거나 아래로만 계속 움직여주기만 하면된다. 따라서 간단하게 생각하면 위로만 움직였을 때 원하는 문자를 찾는 경우와 아래로만 움직였을 때 문자를 찾는 방법 이 두가지 방법을 찾아서 최소값을 구해주면 된다.

 

- 좌우로 움직이는 경우

이 경우가 상당히 복잡하다. 그리디하게 해결할 수 있을 것 같다고 생각되지만 절대로 그리디로는 해결할 수 없는 문제이다. 왜냐하면 "ABAAAB"라는 입력을 처리하기 위해서 그리디로 한 방향으로만 움직이게 된다면 왼쪽으로 움직이는 경우 7, 오른쪽으로 움직이는 경우 7로 7이라고 생각할 수 있다. 하지만 이는 오른쪽으로 한번 가서 위로 한번, 왼쪽으로 두번가서 위로 한번 5번의 시도로 해결할 수 있다. 즉 이는 그리디하게 해결이 불가하며 브루트포스로 모든 경우를 찾아서 해결해주어야한다.

 

브루트포스로 찾아가는 방법은 재귀를 사용하여 왼쪽으로 가는방법과 오른쪽으로 가는 방법을 모두 탐색해주면 된다. 이 때 예외적인 상황으로 A가 연속되어 끝나는 경우(굳이 이동할 필요가 없음)를 따로 처리해주어야한다.

 

3. 세부 해결방안

- 위 아래로 움직이는 경우

public int controlUp(char want) {
    return want - 'A';
}

public int controlDown(char want) {
    return 'Z' - want + 1;
}

좌우로 움직이는 경우는 아스키코드의 연산을 통해 이렇게 구해줄 수 있다. 아래로 내리는 경우는 Z에서 A로 가는 경우를 의미하며 이 때 Z로 이동해야하기 때문에 1을 더해주었다. 위 두 연산을 모두 수행 후 최소값을 넣어주기만 하면 해결할 수 있다.

 

- 좌우로 움직이는 경우

좌우로 움직이는 경우는 재귀로 모든 경우를 탐색하는 브루트포스로 구현해주면된다.

char alphabet = name.charAt(position);
if (alphabet == 'A') {
    boolean[] copyChecked = new boolean[checked.length];
    for (int i = 0; i < copyChecked.length; i++)
        copyChecked[i] = checked[i];
    for (int i = 0; i < name.length(); i++) {
        if (name.charAt((position + i) % name.length()) == 'A')
            copyChecked[(position + i) % name.length()] = true;
        else
            break;
    }

    for (int i = 0; i < name.length(); i++) {
        if (name.charAt((position - i + name.length()) % name.length()) == 'A')
            copyChecked[(position - i + name.length()) % name.length()] = true;
        else
            break;
    }
    for (idx = 0; idx < copyChecked.length; idx++) {
        if (!copyChecked[idx])
            break;
    }
    if (idx == copyChecked.length) {
        min = Math.min(movement-1, min);
        return;
    }
}

이 경우는 연속해서 A로 된 경우에 대한 처리이다. 연속하여 A로 된 경우에는 더이상 움직일 필요가 없기 때문에 이렇게 따로 처리해주어야한다. 이 때 주의해야할 점으로 이동 후 처리를 하는 것이기 때문에서 A로 한번 불 필요한 움직임이 발생한다. 따라서 만약 A로 연속된 경우라면 -1을 해서 처리해야한다.

 

int front = (position + 1) % name.length();
int moveCount = 1;
while (checked[front]){
    front = (front + 1) % name.length();
    moveCount ++;
}
checked[front] = true;
checkRecursive(checked, front, movement + moveCount
        + Math.min(controlUp(name.charAt(front)), controlDown(name.charAt(front))), name);
checked[front] = false;

moveCount = 1;
int back = (position - 1 + name.length()) % name.length();
while (checked[back]){
    back = (back - 1 + name.length()) % name.length();
    moveCount++;
}
checked[back] = true;
checkRecursive(checked, back, movement + moveCount
        + Math.min(controlUp(name.charAt(back)), controlDown(name.charAt(back))), name);
checked[back] = false;

오른쪽으로 이동하는 경우와 왼쪽으로 이동하는 경우를 계산해주기 위해 재귀로 실행되는 코드이다. 재귀를 부르기 전에 이동을 했다는 체크를 하고 이동을 하는 이유는 cheked 배열을 공유하기 때문이다. 만약 재귀로 들어가서 해당 위치를 방문했다고 한다면 다음 재귀로 불러질 때 방문을하지 않은 곳도 방문된 곳으로 판단이 되어 문제가 될 수 있다.

구현코드

package pgm_42860;

public class Solution {
    private int min = Integer.MAX_VALUE;

    public int solution(String name) {
        boolean[] checked = new boolean[name.length()];
        checked[0] = true;
        checkRecursive(checked, 0, Math.min(controlUp(name.charAt(0)), controlDown(name.charAt(0))), name);
        return min == -1 ? 0 : min;
    }

    public void checkRecursive(boolean[] checked, int position, int movement, String name) {
        int idx;
        for (idx = 0; idx < checked.length; idx++) {
            if (!checked[idx])
                break;
        }
        if (idx == checked.length) {
            if(name.charAt(position) == 'A')
                movement --;
            min = Math.min(movement, min);
            return;
        }

        char alphabet = name.charAt(position);
        if (alphabet == 'A') {
            boolean[] copyChecked = new boolean[checked.length];
            for (int i = 0; i < copyChecked.length; i++)
                copyChecked[i] = checked[i];
            for (int i = 0; i < name.length(); i++) {
                if (name.charAt((position + i) % name.length()) == 'A')
                    copyChecked[(position + i) % name.length()] = true;
                else
                    break;
            }

            for (int i = 0; i < name.length(); i++) {
                if (name.charAt((position - i + name.length()) % name.length()) == 'A')
                    copyChecked[(position - i + name.length()) % name.length()] = true;
                else
                    break;
            }
            for (idx = 0; idx < copyChecked.length; idx++) {
                if (!copyChecked[idx])
                    break;
            }
            if (idx == copyChecked.length) {
                min = Math.min(movement-1, min);
                return;
            }
        }

        int front = (position + 1) % name.length();
        int moveCount = 1;
        while (checked[front]){
            front = (front + 1) % name.length();
            moveCount ++;
        }
        checked[front] = true;
        checkRecursive(checked, front, movement + moveCount
                + Math.min(controlUp(name.charAt(front)), controlDown(name.charAt(front))), name);
        checked[front] = false;

        moveCount = 1;
        int back = (position - 1 + name.length()) % name.length();
        while (checked[back]){
            back = (back - 1 + name.length()) % name.length();
            moveCount++;
        }
        checked[back] = true;
        checkRecursive(checked, back, movement + moveCount
                + Math.min(controlUp(name.charAt(back)), controlDown(name.charAt(back))), name);
        checked[back] = false;
    }

    public int controlUp(char want) {
        return want - 'A';
    }

    public int controlDown(char want) {
        return 'Z' - want + 1;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)