프로그래머스

프로그래머스 조이스틱 풀이: 알파벳 변경과 커서 이동 그리디

2026년 9월 14일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 조이스틱
출처: 프로그래머스 코딩테스트 연습, 탐욕법(Greedy)
자체 판단 난이도: Level 3

문자 하나를 바꾸는 상하 이동과 커서를 다음 위치로 옮기는 좌우 이동을 분리해야 한다. 특히 이름 중간의 연속된 A를 건너뛰기 위해 오른쪽과 왼쪽 방향을 섞는 경우를 모두 비교해야 하므로 단순한 순차 그리디보다 구현과 분석이 필요해 Level 3으로 판단한다.

1. 문제 요약

처음에는 모든 문자가 A인 문자열이 주어지고, 조이스틱을 움직여 name을 만들어야 한다.

위쪽 또는 아래쪽 이동으로 현재 문자를 변경한다.
A에서 아래로 이동하면 Z로 순환한다.
왼쪽·오른쪽 이동으로 커서 위치를 바꾼다.
첫 위치의 왼쪽은 마지막 위치이고, 마지막 위치의 오른쪽은 첫 위치다.

문자 변경과 커서 이동을 합한 최소 조작 횟수를 반환한다. 이름 길이는 1 이상 20 이하이고, 이름은 대문자 알파벳으로만 이루어진다.

예를 들어 JAZ는 J를 위로 9번 바꾼 뒤 왼쪽으로 한 칸 이동해 Z를 아래로 한 번 바꾸면 총 11번이다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그리디 선택 기준

총 조작 횟수를 두 부분으로 나눈다.

각 위치의 문자를 A에서 목표 문자로 바꾸는 상하 이동
목표 문자가 A가 아닌 위치를 방문하는 좌우 이동

상하 이동 횟수는 커서가 어떤 순서로 방문하더라도 각 문자마다 독립적이다. 좌우 이동만 방문 순서에 따라 달라지므로, 연속된 A 구간을 건너뛰는 후보를 계산해 최솟값을 선택한다.

세로 이동 비용

문자 char를 만드는 방법은 위로 이동하는 방법과 아래로 이동해 알파벳 순환을 이용하는 방법이 있다.

위쪽 비용 = ord(char) - ord('A')
아래쪽 비용 = ord('Z') - ord(char) + 1

각 위치에서 두 값 중 작은 값을 더한다. 예를 들어 Z는 아래로 한 번 이동하는 편이 위로 25번 이동하는 것보다 짧다.

문자 변경과 좌우 이동을 분리해 계산하기

문자가 A인 위치는 위아래로 바꿀 필요가 없다. 따라서 커서가 모든 위치를 순서대로 방문할 필요도 없다. 어떤 위치 i 뒤에 연속된 A 구간이 있고, 그 구간 다음의 첫 번째 목표 문자가 next에 있다면 해당 A 구간을 건너뛰는 경로를 생각할 수 있다.

기본적으로 오른쪽으로만 이동하면 좌우 비용은 length - 1이다. 하지만 i까지 오른쪽으로 갔다가 방향을 바꾸거나, 먼저 왼쪽으로 돌아 뒤쪽을 처리하면 더 짧을 수 있다.

상태 전이와 경계 처리

각 i에 대해 i + 1부터 연속된 A를 건너뛰어 next를 찾는다. 이후 다음 세 가지 좌우 이동 후보를 비교한다.

처음부터 오른쪽으로만 이동: length - 1
오른쪽으로 i까지 갔다가 돌아가기: 2 * i + length - next
반대쪽을 먼저 처리한 뒤 돌아오기: i + 2 * (length - next)

여기서 length - next는 next부터 문자열 끝까지 남은 거리다. next == length이면 뒤에 더 처리할 문자가 없으므로 해당 후보는 자연스럽게 기본 경로보다 작거나 같아진다. 모든 i에서 후보를 확인하면 연속된 A 구간의 위치에 따른 최솟값을 놓치지 않는다.

그리디 선택이 안전한 이유

상하 이동은 모든 위치를 반드시 목표 문자로 바꾸는 데 필요한 고정 비용이다. 반면 좌우 이동에서 연속된 A 구간을 통과하는 비용은 어떤 순서로 목표 위치를 방문하느냐에 따라 달라진다.

특정 A 구간을 건너뛰는 최적 경로는 한쪽 방향으로 접근한 뒤 반대 방향으로 돌아오는 형태이거나, 반대쪽을 먼저 처리한 뒤 다시 돌아오는 형태 중 하나로 정리할 수 있다. 각 i에서 이 두 왕복 비용과 직진 비용을 비교하므로 가능한 방향 전환의 최솟값을 그리디하게 선택한다.

오답 접근과 반례

커서를 항상 오른쪽으로만 이동하면 연속된 A가 긴 이름에서 불필요한 이동이 생긴다.

name = "JAZ"

오른쪽으로 두 칸 이동하면 J에서 A를 거쳐 Z에 도착하지만, 왼쪽으로 한 칸 이동하면 바로 마지막 위치로 갈 수 있다. 따라서 좌우 이동을 항상 length - 1로 고정하면 정답 11보다 큰 값을 얻는다.

반대로 가장 가까운 다음 목표 문자만 매번 선택해도 이후의 긴 A 구간과 방향 전환 비용을 전체적으로 고려하지 못할 수 있다. 각 연속 A 구간에 대해 오른쪽 우선과 왼쪽 우선 왕복 후보를 함께 비교해야 한다.

시간·공간 복잡도

각 위치에서 다음 목표 문자까지의 연속된 A를 확인하므로 최악의 시간 복잡도는 O(n^2)다. 문제의 이름 길이가 최대 20이므로 충분하다. 추가 배열 없이 비용과 인덱스만 사용하므로 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

def solution(name):
    vertical = sum(
        min(ord(char) - ord("A"), ord("Z") - ord(char) + 1)
        for char in name
    )

    length = len(name)
    horizontal = length - 1

    for index in range(length):
        next_index = index + 1
        while next_index < length and name[next_index] == "A":
            next_index += 1

        forward_then_back = index * 2 + length - next_index
        backward_then_forward = index + (length - next_index) * 2
        horizontal = min(
            horizontal,
            forward_then_back,
            backward_then_forward,
        )

    return vertical + horizontal

vertical은 이름의 모든 문자를 독립적으로 만드는 비용이다. horizontal은 처음에는 오른쪽으로 끝까지 가는 비용으로 시작하고, 각 위치에서 연속된 A 구간을 건너뛰는 두 방향 전환 후보를 비교해 갱신한다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 알파벳 이동과 좌우 경로 선택을 확인할 수 있다.

assert solution("JEROEN") == 56
assert solution("JAN") == 23

4. 공식 예제와 추가 검증

공식 예제와 순환 이동이 유리한 경우, 모든 문자가 A인 경우를 Python 코드로 실행했다.

공식 예제

입력	기대 출력	확인 결과
`"JEROEN"`	56	통과
`"JAN"`	23	통과

추가 검증 1: 마지막 위치로 돌아가는 경우

입력: name = "JAZ"
기대 출력: 11
확인 결과: 통과
검증 목적: 오른쪽 두 칸보다 왼쪽 한 칸 이동이 짧은 경우 확인

추가 검증 2: 변경할 문자가 없는 경우

입력: name = "AAAA"
기대 출력: 0
확인 결과: 통과
검증 목적: 세로·가로 이동이 모두 필요 없는 경계 확인

추가 검증 3: 양끝의 목표 문자와 긴 A 구간

입력: name = "BAAAAAB"
기대 출력: 3
확인 결과: 통과
검증 목적: 가운데 연속된 A를 건너뛰고 양끝 문자를 처리하는지 확인

추가 검증 4: 중간 A 구간에서 방향 전환

입력: name = "BBAAAB"
기대 출력: 6
확인 결과: 통과
검증 목적: 중간 A 구간을 기준으로 왕복 이동 후보를 비교하는지 확인

5. 다른 풀이 방식 검색 및 비교

프로그래머스 공식 문제는 알파벳 변경과 원형 커서 이동의 최소 조작 횟수를 정의한다.
Paul’s Grit의 조이스틱 풀이는 세로 변경 비용을 먼저 계산하고, 연속된 A 구간을 기준으로 직진·왕복 이동 후보를 비교하는 접근을 설명한다.

단순히 모든 커서 이동 경로를 상태 탐색하면 이름 길이에 따라 경우의 수가 늘어난다. 이 글에서는 세로 비용을 독립적으로 계산하고, 좌우 이동은 각 A 구간에서 가능한 방향 전환 후보를 계산해 최소값을 갱신했다. 이름 길이가 짧다는 제한 덕분에 이 방식은 구현이 간단하면서 모든 후보 구간을 안전하게 확인할 수 있다.

마무리

조이스틱은 알파벳을 바꾸는 세로 이동과 커서를 옮기는 가로 이동을 분리해서 생각해야 하는 문제다. 세로 이동은 각 문자의 위·아래 최솟값을 더하고, 가로 이동은 연속된 A 구간을 건너뛰는 직진·왕복 후보를 비교하면 최소 조작 횟수를 구할 수 있다.