문제
In the video game Fallout 4, the quest "Road to Freedom" requires players to reach a metal dial called the "Freedom Trail Ring" and use the dial to spell a specific keyword to open the door.
Given a string ring that represents the code engraved on the outer ring and another string key that represents the keyword that needs to be spelled, return the minimum number of steps to spell all the characters in the keyword.
Initially, the first character of the ring is aligned at the "12:00" direction. You should spell all the characters in key one by one by rotating ring clockwise or anticlockwise to make each character of the string key aligned at the "12:00" direction and then by pressing the center button.
At the stage of rotating the ring to spell the key character key[i]:
1. You can rotate the ring clockwise or anticlockwise by one place, which counts as one step. The final purpose of the rotation is to align one of ring's characters at the "12:00" direction, where this character must equal key[i].
2. If the character key[i] has been aligned at the "12:00" direction, press the center button to spell, which also counts as one step. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.
문제가 좀 길지만, 요약하면 다이얼형태의 자물쇠를 푸는 최소한의 움직임을 구하는 문제이다.
Example 1:
Input: ring = "godding", key = "gd"
Output: 4
Explanation: For the first key character 'g', since it is already in place, we just need 1 step to spell this character. For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo". Also, we need 1 more step for spelling. So the final output is 4.
Example 2:
Input: ring = "godding", key = "godding"
Output: 13
풀이
아이디어
- 이번 키의 알파벳이 여러 개인 경우 각 위치의 최소 돌림 횟수를 구한다.
코드
class Solution:
# 두 위치의 거리를 구하는 함수
def calcDist(self, loc1: int, loc2: int, ln: int) -> int:
return min([abs(loc1-loc2), abs(loc1+ln-loc2), abs(loc2+ln-loc1)])
def findRotateSteps(self, ring: str, key: str) -> int:
# 알파벳의 위치
loc = {}
for i, c in enumerate(ring):
if c not in loc: loc[c] = []
loc[c].append(i)
# 현재 위치와 돌림 횟수
moves = [(0, 0)]
for c in key:
nxt_moves = []
for c_loc in loc[c]:
mn = 100*100
mn_loc = -1
# 다음 위치의 최소 돌림 횟수
for move in moves:
s = self.calcDist(c_loc, move[1], len(ring))+move[0]
if s < mn:
mn = s
mn_loc = c_loc
nxt_moves.append((mn, mn_loc))
moves = nxt_moves
return sorted(moves)[0][0]+len(key)
후기
DP에 어느정도 익숙해져 아이디어는 금방 떠올릴 수 있었고, 구현도 크게 어렵지 않았다.