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

약간의 주저리주저리

• 프로그래머스 색상 #263747 글씨체 Song Myung

시행착오

알파벳 바꾼 후, 좌우로 움직이는 것도 좌/우 한 방향으로만 바꾸면 될 것이라 생각하여 두 방향으로 가서 결과가 더 작은 값을 반환하였다.
=> 판단 미스

맹점

1. 알파벳을 바꾸는 것은 최적화할 필요 없다. 위/아래 한 방향으로만 알파벳을 바꾸도록 한다.
2. 좌우 방향을 바꾸는 것은 연속의 A가 있을 때 방향을 바꿔서 다른 방향으로 가면, 한 방향으로만 가는 것보다 이동을 줄이는 경우가 있다.

   ABAAAB => 이 경우 왼쪽으로(맨끝으로) 갔다가 다시 오른쪽으로 2번 오는 것이 최소.

3. 방향을 두번 이상 바꾸면 최소이동횟수가 절대 안된다.

설명

아까 예시를 든 것처럼 아래 ABAAAAB가 주어졌다고 하자

그럼 한 방향으로 바꿔야 하는 알파벳이 있는 곳까지 가는 게 아니라

한 번 방향을 틀어서 이동하는 게 더 최소비용이 든다.

즉, 우리는 거치지 않아도 되는 이 부분을 찾아야 한다!

for i in range(len(LIST)) 반복문으로 리스트를 돌면서 (완전탐색)
각 지점이 꺾이는 부분일 때 빨간 네모 바깥 옆 원소들(2개)의 인덱스를 찾는다.
그리고, 그 둘 중 한 지점에서 꺾여 이동하면 얼마나 좌<>우로 이동하는지 계산한다.

코드

이 아이디어를 가지고 코드를 작성해보았다.

def solution(name):
    
    length = len(name)
    
    alpha_total = 0
    # 최대 좌우 움직이는 경우: 마지막까지 쭉 한방향으로 가는 거
    move_min = length - 1
    
    # 각 위치에서 조이스틱을 위아래 중 어디로 움직여야 최소로 움직이는지 계산 & 모든 횟수를 더함
    for i in range(length):
        c = name[i]
        
        alpha_total += min(ord(c)-65, 91-ord(c))
        
        # 해당 부분을 꺾이는 부분으로 본다면, 다음부분 A가 몇개 연속으로 있는지 확인
        tmp = i + 1
        while (tmp < length and name[tmp] == 'A'):
            tmp += 1
        
        # 기존 vs 오른쪽으로 갔다가 왼쪽으로 tmp까지 쭉 vs 왼쪽으로 tmp까지 갔다가 오른쪽 i까지 쭉
        move_min = min(move_min, 2 * i + (length-tmp), 2 * (length-tmp) + i)
    
    return alpha_total + move_min