[Programmers] 탐욕법(Greedy) : 조이스틱

코딩테스트 연습 - 조이스틱 | 프로그래머스

📌 문제

➕ 문제설명

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

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

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

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

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

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

➕ 제한사항

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

➕ 입출력 예

📌 풀이

• 내가 접근한 방식 (틀림X)

  위/아래 조작하는 것에 대해서는 몇 번째로 변경하던 상관이 없기 때문에 좌/우 조작하는 것에 핵심이 있다고 생각 했음.

  그래서 현재 위치에서 아직 변경하지 않은 문자 중 오른쪽으로 이동했을 때 가장 가까운 위치의 거리와 왼쪽으로 이동했을 때 가장 가까운 위치의 거리를 비교해서 가까운 쪽으로 이동한다고 생각하고 접근하여 문제를 풀어나갔는데, 여기서 2가지 문제가 발생했다.

  첫번째 문제는 오른쪽으로 가장 가까운 거리와 왼쪽으로 가장 가까운 거리가 같은 경우 어느쪽으로 가야하는지 판단하는 것. 두번째 문제는 왼쪽으로는 무한으로 이동할 수 있지만, 오른쪽으로는 문자열의 끝에 도달하더라도 다시 첫번째로 돌아가지 않는다는 점이다.

  첫번째 문제를 해결하기 위해서 거리가 같을 때 왼쪽은 그 방향으로 그 다음 문자열이 변경할 필요가 있는지 판단해서 필요가 없는 방향쪽을 먼저 이동해서 변경해주도록 수정함. 하지만 여기서 두번째 문제였던 부분이 문제를 일으킨다. 거리가 같을 때 왼쪽으로 먼저 이동해서 문자열의 끝 방향으로 갔을 경우 다시 오른쪽으로 이동하지 못하도록 되어있어 왼쪽으로 계속 이동하는 현상이 발생하여 무조건 수정요소가 적은 방향으로 이동한다는 것도 맞지 않음.

  결국 다른 사람의 풀이를 보게되었음.

• 다른 사람의 접근 방식
  위/아래 조작하는 것에 대해서는 다른 것에 영향을 안 받기 때문에 그냥 문자 비교해서 이동 횟수를 더해주는 방식으로 하였고, 좌/우 조작하는 것에 대해서는 진짜 이동하는 것에 대해서 이동 횟수를 더해준다는 개념보다 문자열을 변경하기 위해서 움직인 경로의 길이를 구하는 개념이다.

  예를 들어, ABAAAABB 를 만들어야 할 때, 기본값으로 첫번째 자리부터 끝까지까지 한쪽방향으로 한번씩 이동해서 변경해주는 값인 문자열 길이 - 1 인 7로 설정해준다. 그 다음, 각 자리를 기준으로 그 자리의 문자까지 오른쪽으로 이동했다가 왼쪽으로 이동해서 만들어줄 때 가장 이동거리를 구한다.

  첫번째 자리일 때, 첫번째 A에서 두번째 자리의 B까지 오기위해서는 왼쪽으로 총 7번을 이동해야 한다. 두번째 자리일 때, 두번째 자리까지 오른쪽으로 1칸 이동 후, 왼쪽으로 3번만 이동하면 문자열을 완성할 수 있다.

  왜냐하면 중간 세번째부터 여섯번째자리까지 4개의 문자는 모두 A이기 때문에 변경해야될 이유가 없다. 즉, 두번째 자리일 경우 총 4번만 이동하여 문자열을 완성시킬 수 있다.

  이와 같은 방식으로 맨 마지막 자리까지 계산해보았을 때, 두번째 자리까지만 오른쪽으로 이동한 경우가 가장 적게 이동하여 문자열을 완성시킨 경우이다.

💻 구현

public class Joystick {

    public static void main(String[] args) {
        String name = "ABAAAABB";
        System.out.println(new Solution().solution(name));
    }

    static class Solution{

        public int solution(String name){
            int answer = 0;
            int len = name.length();

            int min = len - 1;

            for (int i = 0; i < len; i++) {
                char c = name.charAt(i);
                int mov = (c - 'A' < 'Z' - c + 1) ? (c - 'A') : ('Z' - c + 1);
                answer += mov;

                int nextIndex = i + 1;
                while (nextIndex < len && name.charAt(nextIndex) == 'A')
                    nextIndex++;

                min = Math.min(min, (i * 2) + len - nextIndex);
            }

            answer += min;
            return answer;
        }
    }
}