위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다.
대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다.
이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.
상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.
대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.
같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.
예를 들어 1 위에 있던 손가락을 0 으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다. 단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.
숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해주세요.
수많은 맞왜틀 끝에 다다른 또다른 문제... 이건 DP 경험이 부족해서 생긴 일이 아닐까 싶다. 맨 처음엔 브루트포스로 풀려는 뻘짓을 했으니 더더욱.
왼손, 오른손으로 하나의 number를 처리하는 경우의 수는 최대 2가지이므로, 브루트 포스로 풀게 되면 최대 2^100000의 경우의 수를 모두 테스트해봐야 한다. 즉 시간 초과에 걸린다. 따라서 우리는 dp를 적용해 봐야 한다.
잘 생각해 보면, 왼손과 오른손은 처음 시작 위치만 다를 뿐 구분의 의미가 없다. 또한 한 number를 처리할 때 가질 수 있는 최대 경우의 수는 10*9 / 2 = 45가지이다. 문제의 제약 조건 상 같은 숫자를 가리킬 수 없으므로 경우의 수는 더 줄어들게 된다. 즉 이 최대 경우의 수에 대해, 각 경우의 수가 지금의 number를 처리할 때 어떤 가중치로 변화하는지를 체크한다면 O(N)의 시간 내에 처리 가능하다. 이러한 접근법을 가지고 문제를 풀어보자.
weight_cal : 숫자 타자에서, 한 숫자에서 다른 숫자로 이동할 때 가중치가 부여되며 이 가중치를 계산하는 함수이다. 쉽게 생각해 보면 대각선 상에 위치, 직선 상에 위치, 이외의 경우로 생각해 볼 수 있으며 각각의 경우를 쉽게 계산 가능하다.
find_move_weight : 위 weight_cal 함수를 통해 모든 숫자에 대한 경우의 수를 나타내는 이차원 리스트를 완성하는 함수이다.
solution : 메인함수. 앞서 밝힌 알고리즘대로 각 number에 대해 다음 경우의 수를 구하게 되는 DP를 구현하였다. 또한, 각 경우의 수에 대해 최소 가중치를 다음 iteration으로 넘겨주게 된다. 또한 최대 경우의 수를 일일히 테스트해보는 것보다는, 시작 위치에서부터 생성 가능한 경우의 수만을 고려하게 되면 더 연산량이 줄어들게 되므로 이를 고려하였다.
풀이 코드
from collections import defaultdict
MAX = float('inf')
move_weight = [[-1]*10 for _ in range(10)]
num_coord = lambda x : ( (x-1) % 3, (x-1) // 3 ) if x != 0 else (1, 3)
def weight_cal(ix, iy, jx, jy) :
if abs(ix - jx) == abs(iy - jy) :
return 3 * abs(ix - jx) # 대각선방향
if abs(ix - jx) == 0 :
return 2 * abs(iy - jy) # 직선방향
if abs(iy - jy) == 0 :
return 2 * abs(ix - jx)
# 혼합
d_mv = max(abs(ix - jx), abs(iy - jy))
return 3 + 2 * (d_mv - 1)
def find_move_weight():
for i in range(10) :
move_weight[i][i] = 1
ix, iy = num_coord(i)
for j in range(i+1, 10) :
jx, jy = num_coord(j)
weight = weight_cal(ix, iy, jx, jy)
move_weight[i][j] = move_weight[j][i] = weight
def solution(numbers):
find_move_weight()
length = len(numbers)
num_dict = {(4, 6) : 0}
for num in numbers :
num = int(num)
next_dict = defaultdict(lambda : MAX)
for (lnum, rnum), weight in num_dict.items() :
if lnum == num or rnum == num :
next_dict[(lnum, rnum)] = min(next_dict[(lnum, rnum)], weight+1)
continue
lweight, rweight = move_weight[lnum][num], move_weight[rnum][num]
for _weight, _num in [(lweight, rnum), (rweight, lnum)] :
anum, bnum = (_num, num) if _num < num else (num, _num)
next_dict[(anum, bnum)] = min(next_dict[(anum, bnum)], weight+_weight)
num_dict = next_dict
return min(num_dict.values())
