[프로그래머스 Lv.2] 조이스틱(Java) - 그리디

 

📌 핵심 요약

• 상하 이동 — 아래 방향 비용은 'Z' - c가 아니라 'Z' - c + 1이다. 커서는 A에서 출발하므로 A → Z는 1회다.
• 좌우 이동 — length - 1은 최선이 아니다. A는 방문할 필요가 없으므로 되돌아가서 반대편으로 도는 편이 쌀 수 있다.
• 핵심 식 — 왕복하는 구간에만 2가 곱해진다. 종착지가 되는 구간은 1배로 남는다.

 

목차

1 문제 정리

조이스틱으로 이름을 만드는 문제다. 처음에는 모든 자리가 A로 채워져 있고, 목표 문자열이 되도록 조작 횟수를 최소화해야 한다.

프로그래머스 #42860

조이스틱

이름 길이 ≤ 20 · 대문자로만 구성

난이도: Lv.2

조작은 네 가지다. 위/아래는 현재 커서 위치의 알파벳을 바꾸고, 좌/우는 커서를 옮긴다. 커서는 맨 왼쪽에서 시작하며, 좌우 이동은 양 끝이 이어져 있다.

풀이 과정

1. 각 문자를 만드는 데 필요한 상하 조작 횟수를 구해 전부 더한다.
2. 모든 문자를 방문하는 좌우 이동 경로 중 최소 비용을 구한다.
3. 두 값을 합산한다.

상하와 좌우는 서로 영향을 주지 않는다. 어느 순서로 이동하든 각 자리에서 눌러야 할 상하 횟수는 동일하기 때문이다. 따라서 두 문제를 분리해 풀 수 있다고 판단했다.

2 상하 이동 계산

커서가 어떤 자리에 도착했을 때 그 자리의 문자는 항상 A다. 여기서 목표 문자 c로 가는 방법은 두 가지다.

위 방향과 아래 방향

위 방향은 A → B → C 순으로 올라간다. 목표가 c라면 c - 'A'번 누르면 된다. 아래 방향은 A → Z → Y 순으로 내려간다.

여기서 A → Z가 1회라는 점이 중요하다.

목표 문자	위 방향 c - 'A'	아래 방향 (정답)	'Z' - c로 계산하면
A	0	26	25
N	13	13	12
Y	24	2	1
Z	25	1	0

'Z' - c는 Z까지의 거리일 뿐 A에서 Z로 가는 비용이 아니다.

항상 정답보다 1이 작다. 따라서 아래 방향 비용은 'Z' - c + 1이 되어야 한다.

 

Java — 상하 이동 누적

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

3 좌우 이동은 왜 length - 1이 아닌가

처음에는 왼쪽 끝에서 오른쪽 끝까지 한 번 훑으면 되므로 length - 1이라고 생각했다.

그러나 이미 A인 자리는 방문할 필요가 없다. 그 자리를 지나가는 것 자체가 낭비다.

BBBAAAB 추적

길이 7이고 인덱스 0, 1, 2, 6만 방문하면 되는 경우다. 인덱스 3, 4, 5는 이미 A라 들를 이유가 없다.

전략	경로	이동 횟수
쭉 오른쪽	0 → 1 → 2 → 3 → 4 → 5 → 6	6
오른쪽 먼저	0 → 2 (2회) → 되돌아 0 (2회) → 왼쪽으로 6 (1회)	5
왼쪽 먼저	0 → 6 (1회) → 되돌아 0 (1회) → 오른쪽으로 2 (2회)	4

쭉 오른쪽으로 가는 경로는 아무 볼일 없는 A 세 칸을 굳이 밟는다. 되돌아오는 비용을 지불하더라도 A 구간을 건너뛰는 편이 이득일 수 있다는 뜻이다.

ℹ️

양 끝이 이어져 있다

원점(인덱스 0)에서 왼쪽 키를 1번 누르면 마지막 인덱스에 도착한다. 따라서 원점에서 인덱스 j까지 왼쪽 방향으로 가는 비용은 length - j다.

4 turnRight와 turnLeft 수식 분해

두 식이 구하려는 값은 커서가 좌우 화살표를 누른 총 횟수다. 상하 조작은 포함하지 않는다.

변수의 의미

"BBBAAAB"를 기준으로 고정한다.

• 원점(0) — 커서의 시작 위치. 모든 거리는 여기를 기준으로 잰다.
• N (length) — 전체 길이. 여기서는 7.
• i — 원점에서 오른쪽으로 곧장 걸어가 처리할 마지막 지점. 여기서는 2.
• next — i 뒤에 이어지는 A를 전부 건너뛴 뒤 다시 처리해야 할 가장 왼쪽 지점. 인덱스 3, 4, 5가 A이므로 6.

turnRight — 오른쪽 갔다가 되돌아와 왼쪽으로 도는 경로

1. 원점에서 i까지 오른쪽으로 간다. 0 → 1 → 2. 왼쪽 구간을 여기서 다 처리한다. 비용 i = 2
2. i에서 원점으로 되돌아온다. 2 → 1 → 0. 이미 처리한 칸을 되짚는 순수 비용이다. 비용 i = 2
3. 원점에서 왼쪽 방향으로 next까지 간다. 왼쪽 키 1번으로 인덱스 6 도착. 비용 N - next = 1

합산하면 1단계의 i, 2단계의 i, 3단계의 N - next가 더해져 i * 2 + (N - next) = 5가 된다.

💡

왜 i에만 2가 곱해지는가

오른쪽 구간은 갈 때 한 번, 돌아올 때 한 번 총 두 번 밟는다. 반면 왼쪽 구간은 이 경로의 종착지라 돌아올 필요가 없다. 마지막 문자를 바꾸고 나면 커서는 그대로 멈춘다.

turnLeft — 왼쪽으로 먼저 돌았다가 되돌아와 오른쪽으로 가는 경로

같은 틀로 다시 따라간다. 순서만 뒤집힌 경로다.

1. 원점에서 왼쪽 방향으로 next까지 간다. 왼쪽 키 1번으로 인덱스 6 도착. 비용 N - next = 1
2. next에서 원점으로 되돌아온다. 오른쪽 키 1번. 비용 N - next = 1
3. 원점에서 i까지 오른쪽으로 간다. 0 → 1 → 2. 여기가 종착지다. 비용 i = 2

합산하면 1단계와 2단계의 N - next, 3단계의 i가 더해져 (N - next) * 2 + i = 4가 된다.

이번에는 왼쪽 구간이 먼저 갔다가 돌아와야 하는 구간이 되었으므로 2배가 붙었고, i는 종착지가 되어 1배로 남았다.

구분	오른쪽 구간 (i)	왼쪽 구간 (N - next)	BBBAAAB 결과
turnRight	왕복 → 2배	편도 → 1배	5
turnLeft	편도 → 1배	왕복 → 2배	4

두 식은 완전히 같은 구조이고 어느 구간을 왕복할 것인가만 다르다. 짧은 쪽을 왕복해야 손해가 적으므로 두 값 중 작은 쪽을 취한다.

5 연속된 A가 없을 때

A가 흩어져 있는 "BBBABA"로도 확인했다. 길이 6이고 방문해야 할 인덱스는 0, 1, 2, 4다.

i	next	건너뛰는 A	turnRight	turnLeft
0	1	없음	0 + 5 = 5	10 + 0 = 10
1	2	없음	2 + 4 = 6	8 + 1 = 9
2	4	인덱스 3	4 + 2 = 6	4 + 2 = 6
3	4	없음	6 + 2 = 8	4 + 3 = 7
4	6	인덱스 5	8 + 0 = 8	0 + 4 = 4
5	6	없음	10 + 0 = 10	0 + 5 = 5

i = 4일 때 next가 6이 되어 N - next가 0이다. 왼쪽으로 갈 곳이 없다는 뜻이고, 실제 동작은 “그냥 오른쪽으로 인덱스 4까지 걸어가고 멈춘다”가 된다. 인덱스 5의 A까지 갈 이유가 없으므로 length - 1인 5보다 1칸을 아낀다.

"BBBAAAB"에서는 가운데 A 구간을 건너뛰는 것이 이득이었고, "BBBABA"에서는 끝의 A를 밟지 않고 멈추는 것이 이득이다. 같은 식이 두 상황을 모두 잡아낸다.

i = 0의 turnRight가 정확히 5, 즉 length - 1과 같다는 점도 확인했다. i = 0이면 오른쪽 왕복 비용이 0이고 next가 1이라 N - next가 length - 1이 되기 때문이다. 초기값은 사실 이 식의 특수한 경우 중 하나다.

ℹ️

while이 0번 도는 경우

A가 뒤따르지 않는 i에서도 식은 그대로 성립한다. 그때는 “0..i는 오른쪽으로, i+1..N-1은 왼쪽으로 처리”라는 단순한 분할이 되고, 건너뛰는 칸이 없으니 대체로 length - 1보다 나빠질 뿐이다. 별도 예외 처리가 필요 없다.

6 전체 코드

 

Java — Solution.java

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++) {
            // 1. 상하 이동 계산
            char c = name.charAt(i);
            answer += Math.min(c - 'A', 'Z' - c + 1);

            // 2. 연속된 'A'의 끝 위치(next) 찾기
            int next = i + 1;
            while (next < length && name.charAt(next) == 'A') {
                next++;
            }

            // 3. 좌우 이동 계산
            int turnRight = (i * 2) + (length - next);
            int turnLeft  = ((length - next) * 2) + i;
            move = Math.min(move, Math.min(turnRight, turnLeft));
        }
        // 상하 이동 횟수 + 최소 좌우 이동 횟수
        return answer + move;
    }
}

이름 길이가 최대 20이므로 이중 루프여도 최악 400회 수준이다. 규모를 먼저 확인했고, 모든 i를 후보로 놓고 전부 계산해도 부담이 없다고 판단했다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.