[파이썬] 조이스틱 [CODING TEST #49]

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

 

 

처음엔 간단한 문제인 줄 알았으나... 테스트 케이스에서 절반을 틀렸다.

 

알파벳을 바꾸는 위,아래 조작은 아스키 코드로 바꾸는 ord() 함수를 이용하여 쉽게 구현할 수 있다.

 

역시나 문제는 커서를 이동시키는 좌우 조작이었다. 

나의 아이디어는 첫 번째 글자와 인접한 가장 긴 'A'가 있는 반대 방향으로 쭉 가는 것이었다.

그런데 여러 테스트 케이스를 살펴보니 오른쪽으로 갔다가 다시 왼쪽으로 돌아가는 방법이 최단 거리가 되는 케이스가 있었다. 젠장할

 

어떻게 하지.. 해서 찾아보다가 정말 좋은 아이디어를 인터넷에서 봤다.

문자열 중간에 가장 긴 'A'로 연속된 것을 찾고, 그 'AAA...AAA' 문자열 기준 왼쪽을 먼저 방문하는 거리와 오른쪽을 먼저 방문하는 거리, 그리고 일자로 쭉 가는 len(name) - 1 중 최솟값을 alpha를 이동하면서 저장하는 것이다.

 

from collections import deque
def solution(name):
    answer = 0
    min_move = len(name) - 1
    
    # 위아래 조작
    for idx, alpha in enumerate(name):
        if ord(alpha) - ord('A') < ord('Z') - ord(alpha) + 1 : # 다음 알파벳
            answer += ord(alpha) - ord('A')
        else: # 이전 알파벳
            answer += ord('Z') - ord(alpha) + 1
        
        # 실시간 좌우 조작
        right = idx + 1
        while right < len(name) and name[right] == 'A':
            right += 1
            
        # 3가지 중 최단 경로를 갱신
        min_move = min([min_move, 2 * idx + len(name) - right, idx + 2 * (len(name) -right)])
        
    answer += min_move
    return answer

 

그림판으로 그린구린 간단한 설명도 추가

 

 

Reference

https://velog.io/@jqdjhy/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%A1%B0%EC%9D%B4%EC%8A%A4%ED%8B%B1-Greedy