greentea31's Note

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

풀이 과정

A로만 이루어져 있는 글자가 주어질 때, 원하는 문자열로 바꾸려면 조이스틱을 몇 번 조작해야 하는지 구하는 문제이다.

위의 예시를 읽으면서 생각해보면 조이스틱을 위나 아래로 몇 번 조작해야 하는지는 구하기가 간단할 것 같다. A는 0, B는 1, C는 2, ... M은 12, N은 다시 12, O는 11 ... Z는 1번 조이스틱을 조작해서 만들 수 있다.

문자열의 문자를 읽으면서 각 문자에 대응하는 숫자를 조이스틱의 이동 횟수에 더해주면 위, 아래 조작수는 전부 답에 더해진다. 하지만 왼쪽, 오른쪽 조작은 몇 번 해야할까? 문자열의 길이만큼 조작한다고 하기엔 BBAAA는 좌우 이동이 오른쪽으로 한번만 필요한 문자이다.

펜대를 굴려가며 여러 예시를 쓰면서 생각해보면 결국 가장 긴 연속된 A 문자열을 지나가지 않도록 좌우 이동을 해야 최소 이동횟수가 나오겠다는 생각이 든다. 그러면 가능한 최소 경우는 아래와 같다.

1. 그냥 문자열의 길이 - 1 만큼 좌우 이동을 해야하는 경우

ex) BABAB -> 모든 B를 A로 바꿔주려면 결국 4번 이동해야 한다. 다른 방법은 존재하지 않는다.

2. 왼쪽으로 진행하다 꺾어서 오른쪽으로 진행

ex) ABBBBAAAB -> 왼쪽으로 한번 진행후 B를 A로 바꿔준 뒤, 오른쪽으로 가면서 모든 B를 A로 바꿔주는게 최소 경우이다. 좌우 이동횟수 6번이 최소 횟수이다. 문자열의 길이 - 1 = 8보다 적게 이동이 가능함을 알 수 있다. 가장 긴 연속된 A 문자열 AAA 안쪽은 굳이 지나갈 필요가 없기 때문이다.

3. 오른쪽으로 진행하다 왼쪽으로 꺾어서 진행

2번과 비슷한 예시를 생각해볼 수 있다.

소스 코드

def solution(name):
    answer = 0
    minimum_move = len(name) - 1
    
    for i, char in enumerate(name):
    	# 상하 최소 조작 횟수를 구하는 부분
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        nxt = i + 1
        
        while nxt < len(name) and name[nxt] == 'A':
            nxt += 1
            
        # 좌우 최소 이동횟수를 구하는 부분          
        minimum_move = min([minimum_move, 2 *i + len(name) - nxt, i + 2 * (len(name) - nxt)])
        
    answer += minimum_move
    return answer