[Algorithm: 그리디] 프로그래머스 <조이스틱>

Greedy Java Programmers Lv.2

문제

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

프로그래머스

 

---

 

문제 설명

조이스틱으로 알파벳을 만든다. 커서는 맨 앞에서 시작하고, 좌우로 이동하면서 각 위치의 알파벳을 조이스틱으로 조작해 원하는 이름을 완성한다. 최소 조작 횟수를 구하는 문제다.

▲ : 알파벳 +1 (A → B → ... → Z → A)
▼ : 알파벳 -1 (A → Z → Y → ...)
◀ : 커서를 왼쪽으로 (맨 왼쪽에서 누르면 맨 오른쪽으로)
▶ : 커서를 오른쪽으로 (맨 오른쪽에서 누르면 맨 왼쪽으로)

 

문제 분해: 두 문제가 독립적이다

처음엔 상하 이동과 좌우 이동이 얽혀있는 것처럼 보이지만, 사실 이 둘은 완전히 독립적으로 계산할 수 있다.

① 상하 조작 비용 — 각 알파벳을 만드는 최솟값의 합
② 좌우 이동 비용 — 모든 위치를 방문하는 최솟값

최종 답 = ① + ②

 

① 상하 조작 비용

각 알파벳은 위로 올리거나 아래로 내리는 두 가지 방법이 있다. 알파벳은 원형이므로 둘 중 더 짧은 방향을 선택하면 된다.

알파벳 원형 다이얼 (A=0, Z=25)

알파벳 A B C ... N ... Y Z

예시: 'N' 만들기

▲ 위로 A →→→ +13 →→→ N 13번

▼ 아래로 A ←←← -13 ←←← N 13번

→ N은 정중앙이라 어느 방향이든 13번으로 동일

int up = c - 'A'; // 위로 올리는 횟수 
int down = 'Z' - c + 1; // 아래로 내리는 횟수 (원형 연결 고려) 
answer += Math.min(up, down); // 둘 중 최솟값 선택

 

 

② 좌우 이동 비용: 어려운 부분

커서는 인덱스 0에서 시작한다. 모든 A가 아닌 위치를 방문해야 한다. 연속된 A 구간은 건너뛸 수 있으므로, 어떻게 이동하면 가장 적게 이동할 수 있을까?

관찰: 알파벳이 'A'인 위치는 조작이 필요 없다.
연속된 A 구간을 만나면, 왼쪽에서 돌아가는 것과 오른쪽으로 계속 가는 것 중 어느 쪽이 더 짧은지 비교해야 한다.

 

3가지 이동 전략

입력 "JAAN"을 예시로 보자. 인덱스 1, 2가 연속 A이고, 끝에 N이 있다.

예시: "JAAN" (인덱스 1, 2가 연속 A)

J0

A1

A2

N3

i=0 기준, next=3 (인덱스 1, 2는 A이므로 건너뜀 → 처음 나오는 유효 위치)
n = 4, i = 0, next = 3

 

전략 A — 그냥 오른쪽으로 쭉

move = name.length() - 1 = 3 // 0→1→2→3, 3번 이동 (A도 그냥 지나침)

 

전략 B — 오른쪽으로 i칸 갔다가 되돌아와 왼쪽(wrap)으로 접근

i * 2 + (n - next) // 0에서 오른쪽으로 i칸 → 다시 0으로 되돌아오기 i칸 → 왼쪽 wrap으로 끝에서 (n-next)칸
= 0 * 2 + (4 - 3) = 1 // 오른쪽 이동 없이 바로 wrap → 끝에서 N까지 1칸

 

전략 C — 왼쪽(wrap)으로 먼저 접근하고 되돌아와 오른쪽으로

i + (n - next) * 2 // 0에서 왼쪽 wrap으로 끝에서 (n-next)칸 → 다시 0으로 되돌아오기 (n-next)칸 → 오른쪽으로 i칸
= 0 + (4 - 3) * 2 = 2 // wrap 1칸 + 되돌아오기 1칸, 오른쪽 이동 없음

min(3, 1, 2) = 1 → 전략 B 선택: 바로 왼쪽 wrap으로 N 방문

 

공식 직관적으로 이해하기

연속된 A 구간을 피하기 위한 두 가지 우회 전략을 이렇게 생각하면 된다.

이동 전략 시각화 — "NBAAN" (인덱스 1, 2가 A, 끝에 N 존재)

N0

A1

A2

B3

N4

i=0, n=5, next=3 (인덱스 1, 2는 A → 건너뜀, next=3)
전략 A: move = n-1 = 4 (오른쪽으로 쭉)

 

전략 B: i*2 + (n - next)
  0에서 오른쪽으로 i=0칸 → 되돌아오기 0칸 → 왼쪽 wrap으로 끝에서 n-next=2칸 (4→3)
  = 0*2 + (5-3) = 2

 

전략 C: i + (n - next)*2
  왼쪽 wrap으로 끝까지 n-next=2칸 → 0으로 되돌아오기 +2칸 → 오른쪽으로 i=0칸
  = 0 + (5-3)*2 = 4

min(4, 2, 4) = 2 → 전략 B 선택: 바로 wrap으로 오른쪽 끝부터 접근

i = 현재 위치 (여기까지는 이미 방문했다고 볼 수 있음)
next = 연속 A를 건너뛴 뒤 처음 나오는 유효 위치
n - next = 오른쪽 끝에서 wrap해서 접근해야 할 거리

 

 

---

 

전체 코드 흐름

1

move를 "오른쪽으로 쭉 가는 경우"인 n-1로 초기화

2

각 위치에서 상하 조작 비용을 answer에 누적

3

각 위치에서 A 연속 구간의 끝 next를 찾아, 두 가지 우회 전략과 현재 move를 비교해 최솟값 갱신

4

최종 answer + move 반환

 

 

 

최종 코드

class Solution {
    public int solution(String name) {
        int answer = 0;
        int move = name.length() - 1;  // 기본값: 오른쪽으로 쭉

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

            // ① 상하 조작 비용
            int up   = c - 'A';
            int down = 'Z' - c + 1;
            answer += Math.min(up, down);

            // ② 좌우 이동 비용: 연속 A 구간의 끝 탐색
            int next = i + 1;
            while (next < name.length() && name.charAt(next) == 'A') {
                next++;
            }

            // 전략 B: 오른쪽으로 i칸 갔다가 되돌아와 왼쪽으로 우회
            move = Math.min(move, i * 2 + name.length() - next);
            // 전략 C: 왼쪽으로 먼저 우회하고 오른쪽으로
            move = Math.min(move, i + (name.length() - next) * 2);
        }

        return answer + move;
    }
}

 

 

예시 추적: "JAZ"

"JAZ" — 상하 조작 비용 계산

J0

A1

Z2

J: up=9, down=17 → min=9
A: up=0, down=26 → min=0
Z: up=25, down=1 → min=1
상하 합계 = 10

"JAZ" — 좌우 이동 비용 (n=3, 초기 move=2)

i=0: next=2 (인덱스 1은 A, 건너뜀)
  전략 B: 0*2 + (3-2) = 1
  전략 C: 0 + (3-2)*2 = 2
  move = min(2, 1, 2) = 1

i=1: next=2
  전략 B: 1*2 + (3-2) = 3
  전략 C: 1 + (3-2)*2 = 3
  move = min(1, 3, 3) = 1 (변화 없음)

move 최솟값 = 1

최종 answer = 상하(10) + 이동(1) = 11

 

 

---

 

정리

문제 분해

상하 조작과 좌우 이동은 독립적으로 계산 가능. 각각 최솟값을 구해 더한다.

상하 조작

알파벳은 원형. 위로 올리기(c-'A')와 내리기('Z'-c+1) 중 min 선택.

연속 A 구간

A는 조작이 필요 없다. 연속 A 구간을 발견하면 어느 방향으로 우회할지 비교.

두 가지 우회

전략 B: i*2 + (n-next)
전략 C: i + (n-next)*2
매 위치에서 두 값과 현재 move를 min으로 갱신.

복잡해 보이는 문제는 독립된 하위 문제로 분해하는 것이 핵심이다.
좌우 이동에서는 "연속 A 구간을 어느 방향으로 우회하는가"라는 단 하나의 질문으로 좁혀진다.

 

 

 

* 이 포스팅은 Claude AI의 도움을 받아서 작성되었습니다.