길이가 26인 문자열로 키보드 배치를 나타내는 특수한 키보드를 생각해 봅시다. 모든 키가 한 줄에 나란히 배열되어 있고, 인덱스는 0부터 25까지 매겨집니다. 처음에 손가락은 인덱스 0 위치에 놓여 있습니다.
어떤 문자를 입력하려면 손가락을 해당 문자의 인덱스 위치로 이동해야 합니다. 손가락을 인덱스 i에서 인덱스 j로 옮기는 데 걸리는 시간은 |i − j|로 정의됩니다. 따라서 주어진 단어를 입력하는 데 총 얼마나 걸리는지 계산하는 함수를 만들면 됩니다.
예를 들어 키보드 배치가 "abcdefghijklmnopqrstuvwxyz"이고 입력할 단어가 "hello"라면 출력은 20이 됩니다. a에서 h까지는 7, h에서 e까지는 3, e에서 l까지는 7, l에서 l까지는 0, l에서 o까지는 3이므로 전체 이동 시간은 7 + 3 + 7 + 0 + 3 = 20입니다.
문제 해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 각 문자의 인덱스를 저장할 딕셔너리 d를 생성하고, 현재 손가락 위치 z를 0으로 초기화합니다.
- 키보드 배치 문자열 k의 길이만큼 반복하면서 각 문자와 그 인덱스를 d에 저장합니다. 즉, d[k[i]] := i 입니다.
- 누적 시간을 저장할 변수 ans를 0으로 초기화합니다.
- 단어 w의 각 문자 i에 대해 다음을 수행합니다.
- ans에 |d[i] − z|를 더합니다.
- z를 d[i]로 갱신하여 현재 위치를 업데이트합니다.
- 모든 문자를 처리한 후 ans를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 더 잘 이해할 수 있습니다.
class Solution(object):
def calculateTime(self, k, w):
d = {}
z = 0
for i in range(len(k)):
d[k[i]] = i
ans = 0
for i in w:
ans += abs(d[i] - z)
z = d[i]
return ans
ob1 = Solution()
print(ob1.calculateTime("abcdefghijklmnopqrstuvwxyz", "hello"))입력
"abcdefghijklmnopqrstuvwxyz" "hello"
출력
20
이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 입력 단어의 길이입니다. 키보드 배치를 딕셔너리에 미리 저장해 두면 각 문자의 위치를 O(1) 시간에 조회할 수 있어 전체 과정이 매우 효율적으로 동작합니다.