[처음 생각했던 풀이]
1. 현재 커서 위치에서 그 글자까지 최소 몇번을 움직여야 하는가 계산하고,
2. 그 글자 (A)에서 알파벳을 몇 번 바꿔야 최소인가 계산하는 것으로 생각했다...
[문제 풀이]
2. 알파벳이 A가 아닐 때, 변경하는 횟수를 구하는 과정은 쉽다. 아스키 코드를 생각하면 된다.
※ 'A'의 아스키 코드 = 65, 'Z'의 아스키 코드 = 90
1. 이 단계가 중요하다. 알파벳을 변경하려고, 매번 커서를 어느쪽으로 움직여야 할 지 판단하기는 힘들다!
이렇게 생각해보자.
1-1) 커서를 좌우로 움직이는 횟수는, 아무리 최악이어도 문자열을 한 번 순회하면 충분하다. -> N - 1 (최악의 경우)
또는
1-2) 한 쪽 방향(왼쪽/오른쪽)으로 먼저 이동한 다음, 그 반대 방향으로 이동하는 경우에도 최솟값이 있을 수 있다!!!
그렇다면 1-2 단계의 커서 이동 횟수는 어떻게 구할까? (어느 쪽 방향으로 먼저 출발했는 지는 공식 내에서 계산된다!)
(왼쪽 끝에서) 이동한 거리 (left) + (오른쪽 끝에서) 이동한 거리 (right) + left, right 중에서 더 작은 값 (back_distance)
EX) right가 더 작다면, 오른쪽 끝에서 "왼쪽 방향"으로 먼저 이동한 다음, 나머지는 "오른쪽 방향"으로 이동했다는 것이다.
EX) left가 더 작다면, 왼쪽 끝에서 "오른쪽 방향"으로 먼저 이동한 다음, 나머지는 "왼쪽 방향"으로 이동했다는 것이다.
파란색 : 왼쪽 끝에서 움직이지 않았으므로, left = 0
그 대신 오른쪽 끝에서(9번 index) -> 1번 index까지 움직였으므로, right = 9
back_distance = min(left, right)니까 = 0
※ right가 1만큼 더 큰 이유는, 처음 커서의 위치는 0번 index(왼쪽 끝)에 있기 때문이다!!
def solution(name):
count = 0
N = len(name)
for ch in name: # 2. 먼저 커서가 어디있든, A에서 최소로 바꿔야 그 글자가 되는지 모두 계산한다
if (ch != 'A'):
min_up_down = min(ord(ch) - ord('A'), 26 + ord('A') - ord(ch))
count += min_up_down
move = N - 1 # 1. 커서를 좌우로 움직이는 것은, 아무리 최악이어도 문자열을 한번 순회하는 것뿐이다 -> N - 1
for left in range(N):
idx = left + 1
while (idx < N) and (name[idx] == 'A'): # right는 오른쪽 끝에서, left 오른쪽을 기준으로 처음 A가 아닌 알파벳의 위치만큼 빼줘야 한다!
idx += 1
right = N - idx
back_distance = min(left, right) # 한쪽 방향으로 이동 후, 반대 방향으로 이동하는 최소거리를 구한다 -> 그러므로 left나 right 중 최솟값을 한번 더 더하는 것이다.
move = min(move, left + right + back_distance)
count += move
return count