Java] 알고리즘 문제 풀이 - 조이스틱

문제

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력 예

namereturn

"JEROEN"	56
"JAN"	23

출처 

 

 

해법

1. 주어진 문자열 중 문자 'A'를 제외하고 전부 조회한다.

2. 현재 주어진 문자가 'A'부터 시작했을 때 위, 아래로 몇 번 조작해야 하는지 계산한다.

3. 현재 주어진 문자의 조작 횟수, 문자를 조회하기 위해 움직인 횟수를 결과 변수에 더한다.

4. 다음 문자를 조회하기 위해 몇 번을 움직여야 하는지와 해당 위치 값을 계산하고, 기억한다.

 

해당 문제는 탐욕 알고리즘 기법을 사용해야 한다.

탐욕 알고리즘은 '어떤 상황이 있을 때 결과적으로는 최선이 아닐 수 있지만, 당장 지금에는 최선의 방법을 택하는 것'이다. 위 해법 중 '4. 다음 문자를 조회하기 위해 몇 번을 움직여야 하는지와 해당 위치 값을 계산하고, 기억한다.'에 적용되는 개념인데, 만약 "BAAC"라는 문자열이 있고, 현재 첫 문자인 'B'에 대한 조작 계산을 마친 후에 다음 값으로 넘어가야 한다고 해보자.

문자 'A'는 검사를 하지 않으니 넘어가도 되니까 다음 문자는 가장 마지막에 있는 'C'가 될 것이다. 그럼 첫 문자 'B'에서 마지막 문자 'C'까지 가는 방법은 1. 우측으로 3회 이동, 2. 좌측으로 1회 이동이 있다. 이 중 현재를 기준으로 더 좋은 방법은 2. 좌측으로 1회 이동일 것이다.

 

기재한 해법을 좀 더 자세히 설명드려 보자면,

1. 주어진 문자열 중 문자 'A'를 제외하고 전부 조회한다.

   => 해당 인덱스 안에 있는 문자를 조회했는지 여부를 판단하는 bCheck 배열을 만들고, 조회 후에는 true값을 넣는다.

2. 현재 주어진 문자가 'A'부터 시작했을 때 위, 아래로 몇번 조작해야 하는지 계산한다.

   => 'A'~'Z'는 아스키 코드로 65~90이다. 문자 A부터 시작하여 하나씩 증가(A->B)시켜 도달할 때와 하나씩 감소(A->Z)시켜 도달하는 두 가지 경우의 수를 계산한다. 그 코드는 다음과 같다.

name.charAt(curPos) - 65 < ('Z' + 1) - name.charAt(curPos) ? name.charAt(curPos) - 65 : ('Z' + 1) - name.charAt(curPos);

('Z') + 1을 한 것은 'A'에서 'Z'로 이동 시에도 한 번 이동을 하기 때문에 추가해주었다.

3. 현재 주어진 문자의 조작 횟수, 문자를 조회하기 위해 움직인 횟수를 결과 변수에 더한다.

   => 조작 횟수는 위에서 구한 값이고, 문자를 조회하기 위해 움직인 횟수는 'BACC'라는 문자가 있을 때 B를 완료한 이후 C까지 이동하기 위한 횟수이며, 주어진 문자열에서는 1이 될 것이다.

이를 해법 4번보다 먼저 실행하는 이유는, 맨 처음에는 첫 번째 값을 가리킬 것이고, 이 경우에는 위치를 이동할 필요가 없어 위치 이동 관련 변숫값을 0으로 두고 시작하기 때문이다.

4. 다음 문자를 조회하기 위해 몇 번을 움직여야 하는지와 해당 위치값을 계산하고, 기억한다.

   =>이 부분에 대해서는 아까전에 설명을 하였고, 한 문자에 대한 처리를 완료한 후 왼쪽과 오른쪽 중 더 가까운 곳을 찾아 이동하기 위해 필요한 값과 그 위치를 계산하고 기억한다.

 

 

코드

public static int solution(String name) {
        int answer = 0;
        int curPos = 0; // 현재 위치
        int moving = 0; // 다음 위치를 탐색하기 위해 움직인 횟수
        ArrayList<Boolean> bCheck = new ArrayList<>(); // 이미 확인한 위치 또는 'A'인 경우는 TRUE

        for (int i = 0; i < name.length(); i++) {
            if (name.charAt(i) == 'A') {
                bCheck.add(true);
            } else {
                bCheck.add(false);
            }
        }

        // 모든 수를 확인할 때까지 반복
        while (bCheck.contains(false)) {
            int findAlphabet = name.charAt(curPos) - 65 < ('Z' + 1) - name.charAt(curPos) ? name.charAt(curPos) - 65 : ('Z' + 1) - name.charAt(curPos); // 알파벳을 찾기 위해 움직인 횟수

            answer += moving;
            answer += findAlphabet;
            bCheck.set(curPos, true); // 해당 위치 탐색완료 표시

            // 다음 위치 탐색
            if (bCheck.contains(false)) {
                int i = curPos;
                int leftMoving = 0;
                int rightMoving = 0;
                int leftPos = i;
                int rightPos = i;

                // 좌 or 우로 이동시 몇칸을 이동해야 하는지 탐색
                while (bCheck.get(i)) {
                    if (i == 0) {
                        i = name.length() - 1;
                    } else {
                        i--;
                    }
                    leftMoving++;
                    leftPos = i;
                }
                i = curPos;
                while (bCheck.get(i)) {
                    if (i == name.length() - 1) {
                        i = 0;
                    } else {
                        i++;
                    }
                    rightMoving++;
                    rightPos = i;
                }

                // 이동시간이 더 작게든 방향으로 이동(같다면 우측으로 이동)
                moving = leftMoving < rightMoving ? leftMoving : rightMoving;
                curPos = leftMoving < rightMoving ? leftPos : rightPos;
            }
        }

        return answer;
    }

 

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

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