Lv 2. 조이스틱

 

https://school.programmers.co.kr/learn/courses/30/lessons/42860?language=java

프로그래머스

 

 

 

🔠 자바(Java)로 푸는 조이스틱 문제 풀이

🔎 문제 개요

이 문제는 프로그래머스의 "조이스틱" 문제입니다.
주어진 문자열을 "A"로 초기화된 상태에서 목표 문자열로 변경하기 위한 최소 조작 횟수를 구하는 문제입니다.

💡 예제 입력

String name = "JAZ";

💡 예제 출력

11

위 예제에서 JAZ로 만들기 위해 최소 조작 횟수는 11입니다.

---

🛠 알고리즘 접근 방식

이 문제를 해결하기 위해 문자 변경 비용과 커서 이동 비용을 최소화해야 합니다.

✏️ 주요 고려 사항

1. 알파벳 변경 비용
   • 각 문자를 변경할 때 A에서 해당 문자까지 이동하는 비용을 계산해야 합니다.
   • 알파벳은 'A'부터 'Z'까지 26개 존재하며, 위쪽 이동(+)과 아래쪽 이동(-) 중 최단 거리를 선택해야 합니다.
   • 예를 들어 'B'는 A → B (+1)이지만, 'Z'는 A → Z (-1)로 이동하는 것이 더 짧습니다.
   • 이를 일반화하면:

     변경 비용 = min(문자 - 'A', 'Z' - 문자 + 1)
     

2. 커서 이동 비용
   • 문자열의 각 문자를 변경해야 하므로 좌우 이동 비용을 고려해야 합니다.
   • 초기 커서 위치는 0이며, 왼쪽 또는 오른쪽 방향으로 이동하여 최적의 경로를 찾아야 합니다.
   • 연속된 A가 많을 경우, 단순히 끝까지 가는 것보다 중간에 방향을 바꾸는 것이 더 효율적일 수도 있음.

---

🔹 Java 코드 해설

import java.util.*;

class Solution {
    int calculate(char c) {
        return Math.min(c - 'A', 'Z' - c + 1);  // 알파벳 변경 최소 비용 계산
    }

    public int solution(String name) {
        int answer = 0;
        int size = name.length();
        int move = size - 1;  // 기본적으로 왼쪽에서 오른쪽으로 끝까지 가는 경우

        for (int i = 0; i < size; i++) {
            char c = name.charAt(i);
            answer += calculate(c);  // 문자 변경 비용 추가

            // 연속된 'A'를 고려한 커서 최소 이동 거리 계산
            if (i < size - 1 && name.charAt(i + 1) == 'A') {
                int endA = i + 1;
                while (endA < size && name.charAt(endA) == 'A') {
                    endA++;  // 연속된 'A'의 마지막 인덱스 찾기
                }

                // 커서를 되돌아가는 경우와 끝까지 가는 경우 중 최솟값 선택
                move = Math.min(move, i * 2 + (size - endA));
                move = Math.min(move, i + (size - endA) * 2);
            }
        }

        return answer + move;  // 문자 변경 횟수 + 최소 이동 횟수 반환
    }
}

---

🔍 코드 설명

📌 1. 알파벳 변경 비용 계산 (calculate())

int calculate(char c) {
    return Math.min(c - 'A', 'Z' - c + 1);
}

• 'A'에서 목표 문자까지 이동하는 최소 횟수를 반환하는 함수입니다.
• c - 'A' : 'A'부터 c까지 증가하는 거리
• 'Z' - c + 1 : 'Z'에서 c로 감소하는 거리

예제)

• 'B' → min(1, 25) = 1
• 'Z' → min(25, 1) = 1
• 'J' → min(9, 17) = 9

---

📌 2. 커서 이동 계산 (solution())

int move = size - 1;  // 기본적으로 오른쪽 끝까지 이동하는 경우

• 처음에는 커서를 단순히 오른쪽 끝까지 이동한다고 가정합니다.

if (i < size - 1 && name.charAt(i + 1) == 'A') {
    int endA = i + 1;
    while (endA < size && name.charAt(endA) == 'A') {
        endA++;  // 연속된 'A'의 마지막 인덱스 찾기
    }

    move = Math.min(move, i * 2 + (size - endA));
    move = Math.min(move, i + (size - endA) * 2);
}

• 연속된 'A'가 있는 경우, 방향을 바꿔 이동하는 것이 더 효율적일 수도 있음
  1. i * 2 + (size - endA) → 앞쪽에서 되돌아간 후 끝까지 가는 경우
  2. i + (size - endA) * 2 → 먼저 끝까지 간 후 되돌아오는 경우
• move 값을 갱신하여 최소 이동 거리로 업데이트합니다.

---

🔥 시간 복잡도 분석

연산 최악의 경우 수행 횟수 시간 복잡도

calculate() 호출	N	O(N)
for 루프	N	O(N)
while 루프 (연속된 'A' 탐색)	N	O(N)
총합	O(N)

📌 결론
👉 모든 연산이 O(N) 이내로 수행되므로 효율적입니다.

---

🏆 정리

✅ 핵심 포인트

1. 알파벳 변경 최소 비용을 계산한다.
2. 좌우 이동을 최소화하기 위해 최적의 경로를 찾는다.
   • 연속된 'A' 구간을 피하기 위해 되돌아가는 경우와 직진하는 경우를 비교한다.
3. 시간 복잡도 O(N)으로 최적화한다.

🎯 이 알고리즘의 장점

✔ 불필요한 연산을 줄이고 최적의 이동 경로를 탐색
✔ O(N)으로 해결 가능하여 성능이 우수함
✔ 조이스틱 조작 횟수를 최소화하는 최적의 방법 제공

이제 이 방법을 적용하면 조이스틱 문제를 빠르게 해결할 수 있습니다!
💡 효율적인 탐색 기법을 익혀두면, 유사한 문제에서도 유용하게 사용할 수 있습니다. 🚀

---

이 글이 도움이 되었다면, 좋아요와 공유 부탁드립니다! 😊