[프로그래머스] 조이스틱 python (*)

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

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

출처 : 프로그래머스

---

 

코드

def solution(name):
    answer = 0
    # 최소 이동은 문자열 길이 -1
    move = len(name)-1
    
    # 조이스틱 상하 이동으로 알파벳 최소 차이
    for i, alp in enumerate(name):
        answer += min(ord(alp)-ord('A'), ord('Z')-ord(alp)+1)
        
        # 연속된 'A' 발견하면 넘어가기
        moving_idx = i + 1
        while moving_idx < len(name) and name[moving_idx] == 'A':
            moving_idx += 1
            
        # 현재 최소 이동과 조이스틱 좌로 움직이거나 우로 움직이는 것 간의 최소 이동 횟수 구하기
        move = min([move, i*2 + (len(name)-moving_idx), i + 2*(len(name)-moving_idx)])
        
    answer += move
    return answer

풀이

그리디 알고리즘이라기보다는 부르트포스 알고리즘이다.

가능한 경우는 모두 탐색한다.

 

최소 이동은 처음부터 -> 로 계속 이동하는 경우로 문자열 길이 -1 이다.

이제는 조이스틱을 상하 로 이동하는 알파벳 이동의 개수를 구해보자.

A~Z 사이에 있는 알파벳은 A 부터의 조이스틱 이동 횟수와 Z 에서 시작한 조이스틱 이동 횟수의 최소값으로 구한다.

        answer += min(ord(alp)-ord('A'), ord('Z')-ord(alp)+1)

그리고 다시 조이스틱 좌우 이동횟수를 구해야한다.

이 때, A가 있으면 넘어가야한다.

 

그리고 현재 최소 이동 ( 문자열 길이 -1) 와 

A 기준으로 왼쪽에서 움직이거나 A 기준 오른쪽에서 움직이는 이동 횟수 중 가장 최소 값을 구해서

최종 answer에 더해준다.

        # 현재 최소 이동과 조이스틱 좌로 움직이거나 우로 움직이는 것 간의 최소 이동 횟수 구하기
        move = min([move, i*2 + (len(name)-moving_idx), i + 2*(len(name)-moving_idx)])