[알고리즘] 프로그래머스 - 조이스틱

프로그래머스 - 조이스틱

내 풀이

import sys

def get_closest_dists(cursor, name, start_name): # 가로로 움직였을 때 가장 가까운 거리를 찾는 함수
    min_dist, new_cursor = sys.maxsize, cursor
    for i in range(len(name)):
        if name[i] != start_name[i]:
            if min_dist > min(abs(cursor - i), len(name) - abs(cursor - i)):
                min_dist = min(abs(cursor - i), len(name) - abs(cursor - i))
                new_cursor = i

    if min_dist == sys.maxsize:
        min_dist = 0
    return min_dist, new_cursor

def solution(name):
    name = list(name)
    cursor = 0
    start_name = ["A"]*len(name)
    count = 0
    while start_name != name:
        simple_dist = abs(ord(name[cursor]) - ord(start_name[cursor]))
        other_dist = 26 - simple_dist
        count += min(simple_dist, other_dist)
        start_name[cursor] = name[cursor]

        horizon_closest_dist, cursor = get_closest_dists(cursor, name, start_name)
        count += horizon_closest_dist

    return count

세로로 움직였을 때 최단 거리를 찾고, 가로로 움직였을 때의 최단거리도 구해야하는 문제다. 세로로 움직이는 명백히 그리디이고 목표물까지 위로가는 경우, 아래로 가는 경우 두 가지가 있으니 그 중 minimum을 취해야한다.
가로로 가는 경우 오른쪽으로 가는 경우, 왼쪽으로 가는 경우 두 가지가 있으며 그 중 minimum을 취해야한다.

다른 사람 풀이

def solution(name):
    make_name = [min(ord(i) - ord("A"), ord("Z") - ord(i)+1) for i in name]
    idx, answer = 0, 0
    while True:
        answer += make_name[idx]
        make_name[idx] = 0
        if sum(make_name) ==0:
            break
        left, right = 1, 1
        while make_name[idx - left] ==0:
            left +=1
        while make_name[idx + right] ==0:
            right +=1
        answer += left if left < right else right
        idx += -left if left < right else right
    return answer

1. 각 알파벳에 대하여 최소 이동 값을 구한다. (make_name)
2. 값이 0이면 알파벳을 바꿀 필요가 없는 것 들이다. 이외에는 answer에 해당 값을 더한다.
3. 좌우로 이동 방향을 정할 때 바꿔야하는 알파벳이 나오기까지 가장 짧은 거리를 구한다 (부분해)
4. 해당 방향으로 위치를 조절한다. 모든 리스트의 값이 0이 될 때까지 반복한다.

https://jgrammer.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A1%B0%EC%9D%B4%EC%8A%A4%ED%8B%B1