[프로그래머스 lv 2] 조이스틱

사용 언어 - Python3

문제 - 조이스틱

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

프로그래머스

 

 

정답

Greedy 탐욕법 (최적해 도출)

최소한으로 움직이는 경우의 수

abcdefghijklnmopqrstuvwxyz
A로 이루어진 문자열을 최소한의 커서이동을 통해 원하는 알파벳으로 바꿔야한다.

 

1. 상하 이동 = 알파벳 이동

디폴트 = 0

알파벳을 찾을 때 "A부터 오름차순으로 찾기 VS Z부터 내림차순으로 찾기" 중 빠른 방향으로 찾아준다.

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

 

2. 좌우 이동 = 커서 이동

디폴트 = len(name)-1 = 왼쪽부터 쭉 커서 한칸씩 이동하는 경우

문자열 중 A가 있다면, A를 무시하고 반대방향으로 이동하는 게 더 빠를 수 있다.

(예. CCAAAAD -> CC까지 이동하고 오른쪽으로 가서 D만 계산하는 게 최소 조작방법!)

만약 바로 다음 알파벳이 A인 경우, A가 연속 몇개 있는지 next 변수에 저장한 후,

아래 세가지 경우 중 최소값으로 커서를 이동한다.

- 현재까지의 커서 이동

- 왔던 길 돌아가기(i*2) + A의 우측방향에서 시작(len(name)-next)

- A의 우측방향에서 왔던길 돌아가기 (2*(len(name)-next)) + A의 좌측방향에서 시작(i)

 

def solution(name):
    spell_move = 0
    cursor_move = len(name)-1

    for i, char in enumerate(name):
        spell_move += min(ord(char)-ord('A'), ord('Z')-ord(char)+1)
        
        next = i+1
        while next < len(name) and name[next] == 'A':
            next += 1
        
        cursor_move = min([cursor_move, 2*i+len(name)-next,i+2*(len(name)-next)])
    
    return spell_move + cursor_move

 

 

 

레퍼런스

https://bellog.tistory.com/152

[프로그래머스] 조이스틱 - Python

https://aiday.tistory.com/120

[Python] 프로그래머스, 조이스틱 Lv.2 (feat.greedy, Brute Force, 그리디, 완전탐색, 파이썬)