프로그래머스 - 조이스틱

문제 설명

제한사항 및 입출력

풀이

문제가 참 간단명료하다. A로 초기화된 문자열을 상하좌우로 움직여 목표 문자열로 바꾸는 문제이다. 상하는 고정되어있기 때문에 아스키코드를 이용해서 최솟값을 구해주었다. 주의할 점은 좌우로 움직일 때 목표 문자열의 연속된 A 구간을 만난다면 직진하는 것보다 돌아가는 것이 더 빠를 수도 있다는 것이다. 뭔가 수학적으로 접근할 수도 있을 것 같아서 고민을 해보았는데,,, 잘 되진 않았다.

그냥 첫 번째 칸부터 전부 확인하면서 어느 구간에서 꺾는 것이 더 빠른지 모두 계산해주면서 풀이해주었다.

내 코드

def solution(name):
    n = len(name)
    updown = sum(min(ord(c) - 65, 26 - (ord(c) - 65)) for c in name)

    move = n - 1
    for i in range(n):
        j = i + 1
        
        while j < n and name[j] == 'A':
            j += 1
        # 오른쪽으로 i까지 갔다가 왼쪽으로 돌아서 j 이후로 가는 케이스들 비교
        move = min(move, 2 * i + (n - j), i + 2 * (n - j))

    return updown + move

 

매번 move를 갱신할 때 i + 2 * (n - j)도 확인해주었는데, 처음엔 왼쪽으로 가는 경우만 생각해주다가 틀렸다. 생각해보니 연속된 A 구간이 앞쪽에 가깝다면 뒷쪽을 먼저 처리하고 와야하기 때문에 이 경우도 생각해주어야한다... 이 부분이 이 문제의 핵심이었던 것 같다.

 

시간 복잡도는 O(n)이다. 내부 while문에서도 최악의 경우 어차피 순회는 한 번만 일어나기 때문에 n을 벗어나지 않는다.