문제 제목
문제 설명
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동
예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.
- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
제한 사항
name은 알파벳 대문자로만 이루어져 있습니다.
name의 길이는 1 이상 20 이하입니다.
예제 입출력
입력
"JEROEN"
"JAN"출력
56
23풀이
문제 분류는 greedy였다. 문제를 나누자면 크게 두 부분이다. 첫 번째 부분은 조이스틱을 위아래로 움직여서 A를 원하는 스펠링으로 바꾸는 것이고, 두 번째는 커서를 움직여 몇 번째 알파벳을 바꿀지 선택하는 것이다. 또 문제의 두 부분은 완전히 독립적이다.
사실 첫 번째 부분은 전혀 어렵지 않다. 예를 들어 A를 F로 바꾼다고 하면, A->Z->Y->X-> ...->H->G->F로 가는 것보다 A->B->C->D->E->F로 하는 방식이 가장 빠른 방법이다.ord(c)함수를 잘 사용해서 알파벳의 유니코드와 modulo연산을 잘 이용하면 금방 풀 수 있다.
두 번째가 고민할 부분이다. 처음 직관적으로 든 생각은 다음과 같다.
시작점을 기준으로 오직 왼쪽으로만 가거나, 오른쪽으로만 간다. 그중 커서의 움직임의 최솟값을 고른 후 위아래 커서 값의 움직임 횟수만큼 더해준다.
커서를 뒤로 돌리는 움직임을 줄이기 위해서 위와 같은 생각을 했다. 예제의 경우도 잘 통과했다.
그러나 문제점은 항상 생기기 마련이다. 예를 들어서 ABAAAAAAAAABB 같은 입력이 주어지면 매우 비효율적이다.
예시를 들어서 설명하면, 일단 위아래 커서를 움직이는것(A->B or B->A)은 고려하지 않아도 된다. 커서의 좌우 이동방식과 위아래 커서는 독립적이기 때문이다. (생각해보면 쉽다.)
먼저 오른쪽으로만 간다면, A가 아닌 알파벳은 2번,12번,13번이기 때문에 커서의 이동이 총 12번 일어난다. ( 1->2: 1번, 2->12:10번, 12->13:1번)
왼쪽으로만 갈때에도 , 커서의 이동이 12번 일어나기 때문에 총 커서의 움직임은 (12+3)=15번이다.
그러나 실제로 최소의 움직임은 좌우 움직임 4번과 위아래 움직임 3번으로 7번이다.
좌우 움직임이 4번인 이유는 1->2->1->13->12의 커서의 움직임을 보이기 때문이다.
커서가 뒤로 돌리는 것이 사실은 가장 적은 커서 움직임에 필요한 것이다.
천천히 다시 생각해보자. 커서의 움직임을 보면 매 순간마다 자신에게 가장 가까운 A가 아닌 알파벳을 찾으러 가고, 현재의 선택이 미래에 영향을 주는것처럼 보이지는 않다.
그럼 Greedy 알고리즘의 조건을 만족하는 것일까?
그렇지 않다.
Greedy가 아닌 이유
위의 ABAAAAAAAAABB라는 입력에서 커서가 1번일때 두 가지 선택지가 있다.
1.커서를 오른쪽으로 한번 움직여서 2번으로 가기.
2.커서를 왼쪽으로 한번 움직여서 13번(맨마지막)으로 가기.
두가지 선택지 모두 거리상으로 1인 가장 가까운 곳이므로 모두 순간적인 상황에서 최적의 해다.
하지만 13번으로 움직였을때를 잘 생각해보자.
문제의 조건을 다시 읽어보면,
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동
커서를 1번에서 왼쪽으로 이동할때와, 마지막 문자에서 커서를 왼쪽으로 이동할때가 다르다.
13번에서 오른쪽 커서를 입력해서 다시 1번으로 되돌아갈수 없기 때문에 1->13->12->11->...->3->2라는 비효율적인 구조를 가지게 된다. 1번에서의 최적의 선택이 최종적으로는 최적의 해가 아닌것이다.
물론 2번으로 움직일때는 정답이 나온다.
이 문제는 엄밀하게 Greedy하지 않아보인다.(최소한 순간순간 가까운 거리를 선택하는 방식의 Greedy한 풀이는 아니다.) 오른쪽과 왼쪽으로 갈때 길이가 같을때는 오른쪽이 우선되게 풀어야하는 특이한 문제다.
이 문제의 원래 버전(오른쪽으로 커서를 움직였을때 1번으로 돌아올 수 있는)은 백준 3663에 올라와 있다. 3663번 문제는 Greedy로는 쉽게 풀리지 않아 보인다. 완전탐색 같다..
풀이코드
def get_moves(char):
# 알파벳 O부터 Z까지 커서 최소 이동횟수
if ord(char) > ord('N'):
return 26 - ord(char) % 65
# 알파벳 A부터 N까지 커서 최소 이동횟수
else:
return ord(char) % 65
def solution(name):
answer = 0
init_string = ['A'] * len(name)
incorrect_char_idx = list()
# 각 문자마다 변경하는데 드는 최솟값
# 위 아래 커서이동은 좌우 움직임과 무관함
for input_char_and_idx, correct_char in zip(enumerate(name), init_string):
input_char, idx = list(input_char_and_idx)[1], list(input_char_and_idx)[0]
if input_char != correct_char:
answer += get_moves(input_char)
incorrect_char_idx.append(idx)
if len(incorrect_char_idx) != 0:
# 초기 커서는 맨 왼쪽
current_pos = 0
while len(incorrect_char_idx) != 0:
distance_list = list()
# 수정해야할 알파벳의 위치
for idx in incorrect_char_idx:
# 왼쪽 1번 --- 고쳐야할 위치 ----- 현재 위치 라면 ---- 끝위치
# 커서는 왼쪽으로 이동할수밖에 없음
# 오른쪽끝에서 왼쪽 1번으로 갈수는 없음 ( 중요 조건)
if idx <= current_pos:
distance_list.append(current_pos - idx)
# 왼쪽 1번 --- 현재위치 ----- 고쳐야할 위치 ---- 끝 위치 라면
# 두가지 방법이 있음
# -> 이렇게 가서 찾거나
# <- 이렇게 가서 왼쪽 1번에서 끝 위치로 가거나
# 두 방법 중 짧은것을 택해야함
elif idx > current_pos:
distance_list.append(
min((current_pos - idx) % len(name), idx - current_pos))
# 가장 짧게 움직이는것
min_move = min(distance_list)
# 다음 조이스틱의 위치
next_index = incorrect_char_idx[distance_list.index(min_move)]
answer += min_move
# 현재 커서를 가장 거리가 가까운 곳으로 옮김
current_pos = next_index
incorrect_char_idx.remove(next_index)
return answer
프로그래머스 기준 레벨2인데, 2.5 정도는 되는것 같다.
문제에 주어진 제약사항을 잘 읽어야 한다.
Greedy는 매 상황마다 최선을 선택하는것인데 실생활에 매우 적용하고 싶다...
