조이스틱 - Python, 그리디

 

 

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

프로그래머스

 

 

코드 & 풀이

 

def solution(name):
    answer = 0
    size = len(name)

    for ch in name:
        answer += min(ord(ch) - ord('A'), ord('Z') - ord(ch) + 1)

    move = size - 1

    for i in range(size):
        next_idx = i + 1
        while next_idx < size and name[next_idx] == 'A':
            next_idx += 1

        distance = min(i, size - next_idx)
        move = min(move, i + size - next_idx + distance)
    return answer + move

 

위, 아래 키와 왼쪽, 오른쪽 키의 움직임을 따로따로 구합니다.

 

위, 아래 키의 움직임을 구하는건 간단

 

각 알파벳의 유니코드 정수값을 기반으로 작은 쪽을 선택해서 더해주면 됩니다.

 

왼쪽, 오른쪽을 구하는 방법은 조금 골치가 아픕니다.

 

모든 인덱스에서 경우의 수를 구하면 시간이 너무 오래 걸리니

 

각 인덱스마다의 최적의 경우를 구해봅시다.

 

우선 알파벳이 A인 경우는 최대한 피하는게 좋습니다.

 

그렇기에 먼저 A가 아닌 알파벳의 위치를 찾아줍니다.(next_idx)

 

그 후 2가지의 경우를 찾아줍니다.

 

 

 

 

 

 

다음에 또 봐요