[프로그래머스 | JAVA] 조이스틱 🕹️ | 그리디, 탐욕법 | 간결한 코드 | U턴 생각하기

[문제 링크]

프로그래머스

 

[문제]

 

---

 

📍 [코드]

class Solution {
    public int solution(String name) {
        int answer = 0; // 상하 조작 횟수
        int length = name.length();
        
        // 좌우 조작 횟수의 최솟값
        int move = length - 1; 

        for (int i = 0; i < length; i++) {
            char c = name.charAt(i);

            answer += Math.min(c - 'A', 'Z' - c + 1);

            int nextIndex = i + 1;
            while (nextIndex < length && name.charAt(nextIndex) == 'A') {
                nextIndex++;
            }
            
            // 오른쪽으로 i까지 갔다가 U턴해서 뒤부터 방문
            move = Math.min(move, (i * 2) + (length - nextIndex));
            
            // 왼쪽으로 먼저 갔다가 U턴해서 i까지 방문
            move = Math.min(move, (length - nextIndex) * 2 + i);
        }

        return answer + move;
    }
}

 

💡 접근법

이 문제는 두 가지 종류의 조작을 최소화하는 문제입니다.

1. 상하(Up/Down) 조작: 'A'에서 목표 알파벳으로 변경 (예: 'A' -> 'C' 또는 'A' -> 'Y')
2. 좌우(Left/Right) 조작: 커서를 이동하여 'A'가 아닌 모든 문자를 방문

최종 정답은 (모든 상하 조작 횟수의 합) + (좌우 이동 횟수의 최솟값)입니다. 코드는 이 두 부분을 나누어 계산합니다.

1️⃣ 상하 조작 횟수 ( answer 변수 )

for 루프의 첫 번째 부분은 각 문자의 최소 상하 조작 횟수를 구해 answer에 더합니다.

answer += Math.min(c - 'A', 'Z' - c + 1);

• c - 'A': 'A'에서 위로(정방향) 이동하는 횟수입니다. (예: 'C'의 경우 'C' - 'A' = 2)
• 'Z' - c + 1: 'A'에서 아래로(역방향) 이동하는 횟수입니다.
  • 'A'에서 'Z'로 1번 이동 (+1)
  • 'Z'에서 c까지 내려오는 횟수 ('Z' - c)
  • (예: 'Y'의 경우 'Z' - 'Y' + 1 = 1 + 1 = 2)
• Math.min(...): 두 방향 중 더 적게 움직이는 값을 선택합니다. ('A'의 경우 Math.min(0, 26)이 되어 0이 더해집니다.)

2️⃣ 좌우 조작 횟수 ( move 변수 )

이 부분이 문제의 핵심입니다. 'A'가 아닌 모든 문자를 방문하는 최단 경로를 찾아야 합니다.

• int move = length - 1;
  • 먼저, 가장 단순한 경로(오른쪽으로만 끝까지 이동)를 기본 최솟값으로 설정합니다. "BBA"라면 0 -> 1 -> 2 (2번) 이동이므로 length - 1이 됩니다.
• U턴을 고려해야 하는 이유
  • 만약 이름이 "B B A A A B" (길이 6)라면,
  • 방법 1 (오른쪽 직진): 0 -> 1 -> 2 -> 3 -> 4 -> 5. 총 5번 이동합니다.
  • 방법 2 (U턴): 0 -> 1 (1번) -> U턴 (1번) -> 0 -> 5 (왼쪽으로 1번). 총 3번 이동합니다.
  • 이처럼 중간에 'A'가 길게 연속되면 U턴하는 것이 더 빠를 수 있습니다.
• 최소 U턴 경로 탐색 ( for 루프 내부 )
  1. while (nextIndex < ...)
     • 현재 위치 i 다음부터 연속되는 'A'를 모두 건너뜁니다.
     • nextIndex는 'A'가 아닌, 다음에 방문해야 할 문자의 인덱스를 가리키게 됩니다.
     • (예: "B A A B"에서 i=0('B')일 때, nextIndex는 3('B')이 됩니다.)
  2. move = Math.min(move, (i * 2) + (length - nextIndex));
     • 이 코드는 `오른쪽으로 U턴`하는 경로의 비용을 계산합니다.
     • (i * 2): 0에서 i까지 갔다가 (i번) 다시 0으로 U턴 (i번).
     • (length - nextIndex): 0에서 왼쪽으로 nextIndex까지 이동하는 횟수.
     • 의미: [0에서 i까지 방문] -> [U턴] -> [0에서 nextIndex부터 끝까지 왼쪽으로 방문]
  3. move = Math.min(move, (length - nextIndex) * 2 + i);
     • 이 코드는 `왼쪽으로 U턴`하는 경로의 비용을 계산합니다.
     • (length - nextIndex) * 2: 0에서 nextIndex까지 왼쪽으로 갔다가( length - nextIndex번) 다시 0으로 U턴.
     • i: 0에서 i까지 오른쪽으로 이동하는 횟수.
     • 의미: [0에서 nextIndex까지 왼쪽으로 먼저 방문] -> [U턴] -> [0에서 i까지 오른쪽으로 방문]

for 루프가 모든 i를 순회하면서, [기존 move 값(직진)]과 [오른쪽 U턴 값], [왼쪽 U턴 값]을 계속 비교하여 가장 작은 값을 move 변수에 갱신합니다.

3️⃣ 최종 반환

return answer + move;

모든 문자의 상하 조작 횟수 총합(answer)과 모든 'A'가 아닌 문자를 방문한 좌우 조작 횟수의 최솟값(move)을 더하여 반환합니다.

 

 

---

 

💬 마무리

이게 왜 그리디인지.. 이게 왜 레벨2인지.. 정말 어려웠습니다.
이 문제는 좌우 조작은 단순히 오른쪽으로 가는 것 외에도, U턴하는 두 가지 경로 를 모두 계산하여 가장 짧은 경로를 찾는 것이 핵심입니다.
U턴을 어떻게 고려할지에 따라 길거나 짧은 코드가 될 수 있겠으며, 문제 이해 및 난이도에도 큰 차이가 있을 것 같습니다.