프로그래머스 알고리즘 고득점 Kit - [Lv.2] 조이스틱 (Java)

문제 출처 - 링크

알고리즘 분류

• 탐욕법(Greedy)

📋 문제 요약 설명

• 처음 상태는 주어진 이름의 길이만큼 A로만 주어진다.
• 커서는 첫 번째 알파벳에서 시작한다.
• 위, 아래로 조이스틱을 움직이면 알파벳이 변경된다.
  • A에서 아래로 움직이면 Z로 이동한다.
• 오른쪽, 왼쪽으로 조이스틱을 움직이면 커서가 이동한다.
  • 첫 번째 알파벳에서 왼쪽으로 움직이면 커서가 문자의 가장 끝으로 이동한다.
• 주어진 이름에 대해 조이스틱 조작 횟수의 최솟값을 구해라

💡 알고리즘 설계 / 접근 방법

1. 상하 이동 (각 알파벳 변경 횟수) 구하기

   • A가 아닌 알파벳을 변경하는데 A에서부터 변경했을 때랑 Z에서부터 변경했을 때를 비교해서 작은 값을 구하기

2. 좌우 이동 최소값 탐색 구하기

   • 연속된 A구간을 찾아서 아래의 경우를 구하는 식에 사용하고, 이 중 가장 짧은 이동 횟수 구하기
     1. 처음부터 끝까지 이동하는 경우
     2. 오른쪽으로 갔다가 왼쪽으로 돌아오는 경우
     3. 왼쪽으로 갔다가 오른쪽으로 도는 경우

➕ 보완하기 / 성능 비교

• 테스트 케이스 추가

  • 방법 1이 유리한 예시 (문제 예시들)

    • "JEROEN” → 답 56
    • "JAN” → 답 23

  • 방법 2가 유리한 예시

    • "BBBAAAAAB” → 답 8
    • "ABAAAAAAAAAAAB” → 답 5

✅ 풀이

시간 복잡도 → O(N)

1. 상하 이동 : O(N)
2. 좌우 이동
   • for문 : O(N)
   • while문 : 최대 O(N)

class Solution {
    public int solution(String name) {
        int upDown = 0;
        int length = name.length();

        // 1. 상하 이동(각 알파벳 변경 횟수)
        for (int i = 0; i < length; i++) {
            char ch = name.charAt(i);
            // 알파벳을 (A에서부터 변경, Z에서부터 변경 - 알파벳이 A에서 Z로 역순 이동하는 1번을 더해줌)
            upDown += Math.min(ch - 'A', 'Z' - ch + 1); 
        }

        // 2. 좌우 이동 최소값 탐색
        int minMove = length - 1; // 기본은 오른쪽 끝까지 이동

        for (int i = 0; i < length; i++) {
            int next = i + 1;

            // 연속된 A 구간의 끝을 찾음
            while (next < length && name.charAt(next) == 'A') {
                next++;
            }
            System.out.print("next : " + next);

            // 방법 1 : 오른쪽으로 갔다가 왼쪽으로 돌아오는 경우 - 바꿀 문자가 왼쪽에 많고, A 다음 오른쪽이 짧을 때 유리
            // i : 연속된 A구간 전까지 바꿔야 하는 알파벳 수, (length - next) : 연속된 A구간 이후에 바꿔야 할 알파벳 수
            int move = i * 2 + (length - next);

            // 방법 2 : 왼쪽으로 갔다가 오른쪽으로 도는 경우 - 바꿀 문자가 오른쪽에 많고, 앞쪽에서 되돌아가면 유리
            int reverseMove = (length - next) * 2 + i;
            System.out.print(" / move : " + move + " / reverseMove : " + reverseMove);

            // 그 중 최소값 선택
            minMove = Math.min(minMove, Math.min(move, reverseMove));
            System.out.println(" / minMove : " + minMove);
        }

        return upDown + minMove;
    }
}