문제 요약
처음 문자열은 모두 A로 이루어져 있다.
예를 들어 만들고자 하는 이름이 세 글자라면 처음 상태는 다음과 같다.
AAA네 글자라면 다음과 같다.
AAAA조이스틱을 움직여 원하는 이름을 만들어야 한다.
조이스틱 조작은 두 종류로 나눌 수 있다.
알파벳 변경
현재 위치의 알파벳을 바꾼다.
▲ : 다음 알파벳
▼ : 이전 알파벳A에서 위로 움직이면 B, C, D 순서로 이동한다.
A에서 아래로 움직이면 바로 Z가 된다.
커서 이동
현재 커서 위치를 이동한다.
◀ : 왼쪽으로 이동
▶ : 오른쪽으로 이동첫 번째 위치에서 왼쪽으로 이동하면 마지막 위치로 이동한다.
마지막 위치에서 오른쪽으로 이동하면 첫 번째 위치로 이동한다.
목표는 원하는 이름을 만들기 위한 최소 조작 횟수를 구하는 것이다.
핵심 아이디어
이 문제는 크게 두 부분으로 나누어 생각할 수 있다.
- 각 문자를
A에서 원하는 알파벳으로 바꾸는 비용 - 커서를 움직이는 비용
전체 최소 조작 횟수는 다음과 같다.
알파벳 변경 비용 + 최소 커서 이동 비용알파벳 변경 비용은 각 문자마다 독립적으로 계산할 수 있다.
하지만 커서 이동 비용은 단순히 오른쪽으로만 이동하는 것이 항상 최적은 아니다.
중간에 연속된 A가 있다면, 그 구간을 굳이 방문하지 않고 되돌아가는 것이 더 빠를 수 있다.
알파벳 변경 비용
문자 하나를 A에서 원하는 알파벳으로 바꾸는 방법은 두 가지다.
- 위로 이동하기
- 아래로 이동하기
예를 들어 J를 만들려면 위로 9번 이동하면 된다.
A -> B -> C -> D -> E -> F -> G -> H -> I -> J따라서 비용은 9이다.
반면 Z를 만들려면 위로 25번 이동하는 것보다 아래로 1번 이동하는 것이 빠르다.
A -> Z따라서 각 문자의 변경 비용은 다음과 같이 계산할 수 있다.
up = ord(char) - ord("A")
down = ord("Z") - ord(char) + 1
min(up, down)예를 들어 JAZ의 알파벳 변경 비용은 다음과 같다.
J: min(9, 17) = 9
A: min(0, 26) = 0
Z: min(25, 1) = 1총 변경 비용은 10이다.
커서 이동 비용
커서는 처음에 0번 인덱스에 있다.
가장 단순한 방법은 오른쪽으로만 이동하는 것이다.
문자열 길이가 n이라면 오른쪽으로만 이동할 때 최대 이동 횟수는 다음과 같다.
n - 1하지만 연속된 A가 있으면 해당 구간은 수정할 필요가 없다.
그래서 중간에 방향을 바꿔 이동하는 것이 더 좋을 수 있다.
예를 들어 다음과 같은 이름을 생각해보자.
JAZ오른쪽으로만 이동하면 다음과 같다.
0번 J 수정 -> 오른쪽 이동 -> 1번 A -> 오른쪽 이동 -> 2번 Z 수정커서 이동은 2번이다.
하지만 실제 최적 이동은 다음과 같다.
0번 J 수정 -> 왼쪽 이동 -> 2번 Z 수정커서 이동은 1번이다.
따라서 좌우 이동은 연속된 A 구간을 고려해야 한다.
연속된 A 구간 건너뛰기
각 위치 i에서 다음 위치부터 연속된 A가 어디까지 이어지는지 찾는다.
next_index = i + 1
while next_index < n and name[next_index] == "A":
next_index += 1여기서 i까지 갔다가 되돌아가는 경우와, 뒤쪽부터 먼저 처리하는 경우를 비교한다.
이동 경우 1: 오른쪽으로 갔다가 되돌아가기
2 * i + n - next_index의미는 다음과 같다.
i까지 오른쪽으로 이동- 다시 시작점 쪽으로 되돌아감
- 뒤쪽의 수정할 문자로 이동
이동 경우 2: 뒤쪽부터 처리한 뒤 되돌아오기
i + 2 * (n - next_index)의미는 다음과 같다.
- 뒤쪽으로 먼저 이동
- 다시 돌아와 앞쪽을 처리
두 경우 중 더 작은 값을 현재 최소 이동 횟수와 비교한다.
move = min(move, 2 * i + n - next_index)
move = min(move, i + 2 * (n - next_index))전체 코드
def solution(name):
n = len(name)
answer = 0
for char in name:
up = ord(char) - ord("A")
down = ord("Z") - ord(char) + 1
answer += min(up, down)
move = n - 1
for i in range(n):
next_index = i + 1
while next_index < n and name[next_index] == "A":
next_index += 1
move = min(move, 2 * i + n - next_index)
move = min(move, i + 2 * (n - next_index))
return answer + move예제: JAZ
name = "JAZ"처음 상태는 다음과 같다.
AAA목표는 다음과 같다.
JAZ알파벳 변경 비용
J: 9
A: 0
Z: 1총 알파벳 변경 비용은 다음과 같다.
9 + 0 + 1 = 10커서 이동 비용
처음 커서는 0번 인덱스에 있다.
0번 위치에서 J를 만든 뒤, 왼쪽으로 한 번 이동하면 마지막 위치로 이동한다.
마지막 위치에서 Z를 만들면 된다.
따라서 커서 이동 비용은 1이다.
최종 조작 횟수는 다음과 같다.
10 + 1 = 11결과:
11시간 복잡도
문자열의 길이를 n이라고 하자.
알파벳 변경 비용을 계산할 때 문자열을 한 번 순회한다.
커서 이동 비용을 계산할 때도 각 위치에서 연속된 A 구간을 확인한다.
전체 시간 복잡도는 다음과 같다.
O(n^2)다만 프로그래머스 원래 제한에서는 문자열 길이가 작기 때문에 충분히 통과할 수 있다.
그리고 실제로는 연속된 A 구간을 확인하는 비용이 크지 않아 효율적으로 동작한다.
공간 복잡도는 추가 배열을 사용하지 않으므로 다음과 같다.
O(1)정리
조이스틱 문제는 두 비용을 나누어 생각하는 것이 핵심이다.
- 알파벳 변경 비용
- 커서 이동 비용
알파벳 변경 비용은 각 문자마다 위로 가는 경우와 아래로 가는 경우 중 작은 값을 더하면 된다.
커서 이동 비용은 단순히 오른쪽으로만 가는 것이 아니라, 연속된 A 구간을 건너뛰는 경우를 고려해야 한다.
따라서 각 위치에서 다음 연속된 A 구간을 찾고, 방향을 꺾는 두 가지 경우를 비교하면 최소 이동 횟수를 구할 수 있다.
