[프로그래머스/파이썬] 조이스틱

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

프로그래머스

이 문제의 포인트는 2가지이다.

 

1. A에서 해당 알파벳으로 가는 최소 횟수 구하기

2. 현재 위치에서 왼쪽과 오른쪽 어디로 갈 것 인지 정하기

 

1번은 사실 정해져있다

아스키코드를 이용해 풀이하면, 중간 인덱스를 기준으로 A에서 출발하는 것이 빠른지 아니면 Z로 이동해서 거꾸로 가는 것이 빠른지 알 수 있기 때문이다. 

 

그렇다면 중요한 것은 2번인데

어떻게 풀지 생각해보면, 가장 중요한 포인트는 "연속된 A가 있을 경우, 반대쪽으로 피해가자" 이다'

 

그러나 무작정 피해가면 안된다,, 왜?

 

1) BBAAAAAAAABBBB

 

2) BBBBAAAAAAAABB

 

두 예시를 보자. 일단 한눈에 봐도 저 AAAA는 그냥 지나가면 손해일 것 같다.

 

1번 예시는 B에서 출발하여 바로 맨 뒤로 이동하는 것이 이득이다.

2번 예시는 일단 BBBB로 갔다가 다시 맨 처음 B로 돌아와서 맨 뒤에 있는 B로 이동하는 것이 가장 좋다

 

그렇기 때문에, 매 상황마다 연속된 A들을 기준으로 계속 진행 방향대로 갈지, 반대로 꺾을지 결정해야 한다.

def solution(name):
    answer = 0
    min_move = len(name) - 1

    # 위 아래 이동 횟수
    for idx in range(len(name)):
        
        ascii = ord(name[idx]) - 65
        
        if ascii > 13:
            answer += 26 - ascii

        else: answer += ascii            
    
    # 연속된 A 찾아서 좌우 이동 최적화
    for i in range(len(name)):
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
        min_move = min([min_move, 2 * i + len(name) - next, i + 2 * (len(name) -next)])
    answer += min_move
    return answer

코드 설명

min_move = min([min_move, 2 * i + len(name) - next, i + 2 * (len(name) -next)])

쉽게 말해서

1) 그냥 쭉 전진 (min_move)

2) A의 왼쪽 부분 먼저 탐색하고 되돌아가서 오른쪽 부분 탐색

3) A의 오른쪽 부분 먼저 탐색하고 되돌아가서 왼쪽 부분 탐색

 

이 3가지 경우를 계속해서 비교하며 최적의 이동 횟수를 찾는 것이다