[프로그래머스][탐욕법] 조이스틱

programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱

해결방법

글자를 바꿔야할 문자중 현재커서에 가장 가까운 곳을 선택하며 글자를 바꿔나가면 된다.

 

가장 가까운곳을 구하는 방법은 heapq를 이용하였다.

 

import heapq
def solution(name):
    length = len(name)
    cursor = 0
    answer = 0
    currentName = ['A'] * length
    while currentName != name : 
        q = []
        for i in range(length):
            if currentName[i] != name[i]:
                heapq.heappush(q,[min(abs(cursor-i), length - abs(cursor-i)), i])
                print(q)
        if q:
            cursor = q[0][1]
            answer += q[0][0]
            answer += min(ord(name[cursor]) - ord('A'), ord('Z') + 1 - ord(name[cursor]))
            currentName[cursor] = name[cursor]
        else:
            break

    
    return answer

 

코드 설명

 

min(abs(cursor-i), length - abs(cursor-i))

커서를 오른쪽으로 움직여서 가거나 왼쪽으로 움직여서 가는것중 짧은걸 의미

 

min(ord(name[cursor]) - ord('A'), ord('Z') + 1 - ord(name[cursor]))

글자를 위로 또는 아래로 움직여 가장 횟수가 적은 방법 선택

 

 

 

즉

 

커서 움직일때 왼쪽, 오른쪽중 가장 가까이 있는걸 선택

문자를 바꿀때 위 아래로 바꾸는것중 횟수가 가장 적은걸 선택