42860. 조이스틱 (탐욕법)

조이스틱

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

• 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
• 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
• 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
  따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

아이디어

각 문자가 변화하는 순서는

	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A
번호	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	0
이동 횟수	0	1	2	3	4	5	6	7	8	9	10	11	12	13	12	11	10	9	8	7	6	5	4	3	2	1	0

위, 아래 이동 횟수

1. 알파벳 번호 - A의 번호(=0)
2. Z의 번호(=25) - 알파벳 번호 + 1

좌, 우 이동 횟수

1. 한 쪽 방향(좌, 우)으로 모든 문자 순회
   최대 N-1회 이동
2. 한쪽 방향으로 이동 후 반대방향으로 이동

코드

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

	# 아스키코드 번호 차이로 이동 횟수 구하기
    for ch in name:
        answer += min(ord(ch) - ord('A'), ord('Z') - ord(ch) + 1)

    move = n - 1
    for left in range(n):
        idx = left + 1
        while (idx < n) and (name[idx] == 'A'):
            idx += 1
            
        right = n - idx
        distance = min(left, right)
        
        move = min(move, left + right + distance)
        
    answer += move
    return answer