프로그래머스 lv2 조이스틱

출처

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

풀이

def solution(name):
    name = list(name)
    return upAndDown(name)+leftAndRight(name)

# 위아래로 움직여서 알파벳을 맞추는것은
# 'A'에서 'Z' 방향으로 맞추는방법과 역방향으로 맞추는 방법중 최적의 방법을 선택하면 된다.
def upAndDown(name):
    A, Z = ord('A'), ord('Z')
    return sum(min(ord(c)-A, Z-ord(c)+1) for c in name)

# 왼쪽, 오른쪽으로 깊이 우선탐색되는지 체크하여
# 최적의 답을 백트래킹하여 구하면 된다.
def leftAndRight(name):
    N = len(name)
    joystick = ['A']*N
    cost, GET = [len(name)-1], 0
    
    def dfs(pos, curCost):
        if joystick == name:
            cost[GET] = min(cost[GET], curCost)
            return
        
        if cost[GET] == curCost:
            return
        
        for newPos in ((pos+1)%N, (pos-1)%N):
            temp = joystick[newPos]
            joystick[newPos] = name[newPos]
            dfs(newPos, curCost+1)
            joystick[newPos] = temp
        
    joystick[0] = name[0]
    dfs(0, 0)
    return cost[GET]