[고득점 Kit / 탐욕법 ] 조이스틱 (feat.ord)

https://school.programmers.co.kr/learn/courses/30/lessons/42860?language=python3

프로그래머스

 

이 문제를 해결하기 위해서는 2가지를 고려해야 한다.

 

 

1. 알파벳을 맞추기 위한 조작 횟수 계산

• 각 문자를 'A'에서 원하는 알파벳으로 바꾸는 데 필요한 최소 조작 횟수는 위쪽(▲) 혹은 아래쪽(▼)으로 이동했을 때 더 짧은 방향으로 선택
• 각 알파벳에 대해, min(위로 이동하는 횟수, 아래로 이동하는 횟수)로 계산
  • 위로 이동하는 횟수는 해당 알파벳의 순서(예: 'B'는 1번, 'C'는 2번...)
  • 아래로 이동하는 횟수는 26에서 위로 이동하는 횟수를 뺀 값

2. 커서 이동 최적화

• 커서를 오른쪽(▶)으로 이동하면서 알파벳을 변경하지만, 때에 따라 왼쪽(◀)으로 돌아가는 것이 더 효율적일 수 있다.
• 모든 경우를 고려해 커서 이동의 최솟값을 찾는 것이 핵심!

 

코드를 살펴보자.

def solution(name):
    # 알파벳 변경 횟수 계산
    def get_char_move(c):
        return min(ord(c) - ord('A'), ord('Z') - ord(c) + 1)
    
    # 총 이동 횟수 초기화
    total_moves = 0
    n = len(name)
    
    # 각 문자에 대해 위, 아래로 움직이는 횟수 합산
    for char in name:
        total_moves += get_char_move(char)
    
    # 좌우 이동 최소 횟수 계산
    min_move = n - 1  # 오른쪽으로 쭉 가는 경우를 기본으로 설정
    
    for i in range(n):
        next_idx = i + 1
        
        # A가 연속으로 나오는 구간의 끝을 찾음
        while next_idx < n and name[next_idx] == 'A':
            next_idx += 1
        
        # 현재 위치에서 연속된 A 이후로 커서를 이동하는 경우 계산
        min_move = min(min_move, 2 * i + n - next_idx, i + 2 * (n - next_idx))
    
    total_moves += min_move
    return total_moves

 

 

get_char_move 함수는 각 알파벳을 'A'에서 원하는 알파벳으로 바꾸는 데 필요한 조작 횟수를 계산한다.

그리고, 각 문자에 대해 위, 아래로 움직이는 횟수를 구해서 합한 값을 total_moves에 저장한다.

 

for i in range(n):
    next_idx = i + 1
    
    # A가 연속으로 나오는 구간의 끝을 찾음
    while next_idx < n and name[next_idx] == 'A':
        next_idx += 1

 

 

• A의 연속 구간 탐색: 이 부분은 현재 위치 i에서 연속된 'A' 구간이 어디까지 이어지는지를 찾는 과정이다. next_idx는 다음 커서의 위치를 가리키며, 만약 name[next_idx]가 'A'라면, 그 다음 인덱스로 계속 이동하면서 'A'가 끝나는 지점을 찾는다.
• 이동 경로 계산: 연속된 'A' 구간을 찾은 후, 커서를 어떻게 이동하는 것이 최적인지 계산한다. 여기서 이동 경로의 경우의 수는 크게 3가지다.

 

min_move = min(
    min_move, 
    2 * i + n - next_idx,  # 현재 위치까지 갔다가 다시 돌아서 끝으로 이동하는 경우
    i + 2 * (n - next_idx) # 연속된 A를 넘어서 가는 경우
)

 

 

1. 첫 번째 경로: 2 * i + n - next_idx

• i는 현재 커서 위치
• 이 경로는 현재 위치에서 시작해 첫 번째로 연속된 'A'가 시작되기 전에 돌아서 끝까지 이동하는 경우를 의미한다.
• 2 * i는 오른쪽으로 갔다가 다시 왼쪽으로 돌아오는 이동을 뜻함
• n - next_idx는 그 후 남은 문자열을 끝까지 쭉 이동하는 것

2. 두 번째 경로: i + 2 * (n - next_idx)

• 이 경로는 커서를 그냥 처음부터 왼쪽으로 가는 경로
• i는 시작 지점에서 앞으로 가는 거리를 의미하고, 2 * (n - next_idx)는 커서가 앞으로 가다가 연속된 'A'를 건너뛰고 그 다음 문자로 이동하는 것을 의미한다.

즉, min_move에 커서 이동의 최소 값을 구해 넣는다. min_move는 처음엔 그냥 오른쪽으로만 쭉 가는 경우로 설정하고(n-1), 이보다 더 효율적인 경로가 있는지를 계산하는 것이다.