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

1. 문제 - 프로그래머스 조이스틱

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

 

이 문제는 다른 사람의 풀이를 보고 이해해보고자했다. 

 

✅ 풀이

def solution(name):
    answer = 0
    n = len(name)

    for ch in name:       # 1)
        if (ch != 'A'):
            min_up_down = min(ord(ch) - ord('A'), 26 - (ord(ch) - ord('A'))
            answer += min_up_down

    move = n - 1          # 2)
    for left in range(n):
        idx = left + 1
        while (idx < n) and (name[idx] == 'A'):
            idx += 1
            
        right = n - idx
        distance = min(left, right)
        move = min(move, left + right + distance)

    answer += move
    
    return answer

 

이 문제는 조이스틱을 최소로 조작하여 A로 이루어진 name길이의 문자열을 input값까지 바꾸는 것이 목적임을 먼저 인지하고 시작하자.

 

1) 커서가 어디에 있는지와 무관하게, A에서 해당 알파벳까지 가기 위해 ▲ (다음 알파벳), ▼ (이전 알파벳) 으로 이동하는 방법 중 최소값을 더한다.

- ord(chr) - ord('A'): A에서 알파벳까지의 거리 --> ▲ 을 누르는 횟수

- 26 - (ord(chr) - ord('A')): A에서 이전 알파벳으로 이동함으로써 (A -> Z -> Y -> ...) 이동하는 거리 --> ▼ 을 누르는 횟수

 

2) move는 커서를 좌 혹은 우로 움직인 횟수의 최소값이다.

 

    for left in range(n):
        idx = left + 1
        while (idx < n) and (name[idx] == 'A'):   # A인 애들은 커서를 누를 필요가 없으니 건너뛰어도 된다. A가 아닌 알파벳 찾기
            idx += 1
            
        right = n - idx
        distance = min(left, right)
        move = min(move, left + right + distance)

 

- for left in range(n): 우선 커서를 계속 오른쪽으로 이동하면서 A가 아닌 알파벳을 찾고, 그 위치에서의 커서 좌우 횟수를 비교한다고 가정한다.

- 그 다음 A가 아닌 알파벳을 찾고 (커서로 이동해야하는 위치)

- right = n-idx: 그림에서처럼 왼쪽 커서를 통해 왼쪽으로 누르는 경우와 비교한다.

- distance는 왼쪽 혹은 오른쪽으로 갔다가 다시 반대 방향으로 돌아가보는 경우의 수이다.

 

EX) right가 더 작다면, 오른쪽 끝에서 "왼쪽 방향"으로 먼저 이동한 다음, 나머지는 "오른쪽 방향"으로 이동했다는 것이다.

EX) left가 더 작다면, 왼쪽 끝에서 "오른쪽 방향"으로 먼저 이동한 다음, 나머지는 "왼쪽 방향"으로 이동했다는 것이다.

 

따라서 distance는 min(left, right)으로 둘 중 최소값에 해당하고, 해당 값을 같이 더해준다.

 

이렇게 해서 구한 move의 최소값을 answer에 더하면 된다.