[탐욕법(Greedy)] 조이스틱

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

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

 

상하 조이스틱과 좌우 조이스틱을 따로 계산한다.

상하 횟수는 구하기 쉽고, 좌우의 경우는 그리디 알고리즘에 따라, 그 순간순간 가장 가까운 위치로 커서를 이동하면서 해를 구하면된다.

def solution(name):
    answer = 0
    name = list(name)
    a = 'ABCDEFGHIJKLM_ ZYXWVUTSRQPON'
    #상하 계산
    for i in name:
        answer += a.find(i)%14
    #좌우 계산
    i = 0
    name[0] = 'A'
    while True:
        left, right = 1, 1
        for j in range(1, len(name)):   #왼쪽으로 탐색
            if name[i-j] == 'A': left += 1
            else: break
        for j in range(1, len(name)):   #오른쪽으로 탐색
            if name[i+j] == 'A': right += 1
            else: break
        if left < right:
            answer += left
            i -= left
        else:
            answer += right
            i += right
        name[i] = 'A'
        if name.count('A') == len(name):
            return answer