[프로그래머스] lv2. 조이스틱

https://school.programmers.co.kr/learn/courses/30/lessons/42860

작년에 알고리즘 고득점 kit를 풀다가 포기한 기억이 있다.
이번에도 혼자서는 못풀어서, 다른 사람들의 풀이를 참고했다.

우선 정답을 받은 코드는 다음과 같다.

def change_alpha(alpha):
    forward_dir = abs(ord('A') - ord(alpha))
    backward_dir = abs(ord('Z') - ord(alpha)) + 1 # 'z'로 바꾸는 1회
    return min(forward_dir, backward_dir)
    
def solution(name):
    name = list(name)
    total_move = 0
    min_move = len(name) - 1
    for i, n in enumerate(name):
        total_move += change_alpha(n)
        next = i+1 # 'A'가 아닌 다음 문자 위치
        while next < len(name) and name[next] == 'A':
            next += 1
        min_move = min(min_move, i * 2 + len(name) - next, 2 * (len(name) - next) + i)
        
    total_move += min_move
    return total_move

상하이동조건은 쉽게 생각할 수 있는데, 좌우이동조건이 까다로웠다.
처음에는 "그리디니까, 현재 위치에서 가장 가까운 A가 아닌(아직 맞춰지지 않은) 알파벳의 위치까지의 거리를 합하다보면 최소겠지?" 라고 생각했는데, 이런 반례가 있었다.

이 경우, 위의 풀이를 적용하면 총 11번 이동하게 된다.

그런데 실제 최소 이동거리는 10이다.

그래서 결국 풀이를 보게 되었고, 좌우이동거리는 3가지 경우로 나뉜다는 것을 알게되었다.

• 한쪽으로 쭉 가는 경우
  • 이 경우 좌우이동거리는 len(name)이 된다.
• 오른쪽으로 갔다가 왼쪽으로 꺾는 경우
• 왼쪽으로 갔다가 오른쪽으로 꺾는 경우

꺾는 두 가지의 경우는 최대 길이의 A를 기준으로 꺾게 된다.

위의 경우를 확인해보자.
'AAA'부분은 꼭 들러야 하는 부분이 아니기 때문에, 피해가는 것이 이득일 수 있다. 실제로 오른쪽으로 갔다가 기다란 A들을 만나고 왼쪽으로 꺾는 경우가 최소 좌우이동거리이다.

위의 두 경우는 코드에서 i가 2일때 계산하게 된다. (for문을 통해 next가 6이 된다.)

• 오른쪽으로 갔다가 왼쪽으로 꺾는 경우
  • 2 * i + len(name) - next
• 왼쪽으로 갔다가 오른쪽으로 꺾는 경우
  • i + 2 * (len(name) - next)