[Python] 조이스틱(그리디)

프로그래머스

문제 설명

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

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

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

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력 예

---

제출

def solution(name):
	answer = 0
    move_cnt = len(name) -1
    
    for i, spell in enumerate(name):
    	answer += min(ord(spell) - ord('A'), ord('Z') - ord(spell) +1)
        
        next = i + 1
        
        whihle next < len(name) and name[next] == 'A':
        	next += 1
            
        move_cnt = min[move_cnt, 2 * i + len(name) - next, i + 2 * (len(name) - next)])
        
	answer += move_cnt
    
    return answer

 

💬 후기

이거 그리디 .. 맞나 .. 요 ? 그리디가 익숙하다가도 이해가 잘 안됨

처음에는 알파벳을 A부터 Z까지 다 작성도 해보고 ..

결국 실패 ..

그리디인 이유는 상하 움직이고 좌우 움직일때 덜 움직이는 방향을 선택해야하기 때문이라고 한다.

1. 상 - 하 방향의 관점

∙ A 부터 오름차순으로 알파벳을 찾는게 빠를지, Z부터 내림차순으로 찾는게 빠를지 비교한다.

∙ 각 알파벳마다 상하조정 중 min 값으로 최소 횟수를 담아두는 배열을 만든다.

 

2. 좌 - 우 방향의 관점

∙ 왼쪽에서 오른쪽으로만 이동하는 경우 +A가 나올때까지 반대 방향으로 이동하는 경우를 비교한다.

 

참고

[Programmers][그리디] 조이스틱 python (211031)

 

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

 

Tip.

위로가는거랑 아래로가는 값의 최솟값을 answer에 저장 ~

좌/우 방향에서 2를 곱하는 이유는 잘 모르겠다 ?