[Greedy] 조이스틱

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

프로그래머스

 

조이스틱 상하 방향은 원형 큐나 아스키코드 변환하는 함수인 ord()를 이용하여 쉽게 계산할 수 있습니다.

'조이스틱'문제는 'A'문자열이 존재할 때, 좌우 방향을 최소화 하는 것이 핵심입니다.

 

사실, 이 문제는 연속된 'A'문자열 중 최소 이동 횟수를 계산해야 하기 때문에 가장 작은 또는 큰 값을 계속 선택해 나가는 그리디보다는 완전 탐색에 가깝습니다. 

 

코드는 다른 사람의 풀이를 참조했습니다.

def solution(name):
    answer = 0
    
    # 순차적 최소 이동 횟수
    min_move = len(name) - 1
    
    for i, char in enumerate(name):
    	# 알파벳 최소 변경 횟수
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        
        # 해당 알파벳 다음부터 연속된 A 문자열 찾기
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
            
        # 기존, 연속된 A의 왼쪽시작 방식, 연속된 A의 오른쪽시작 방식 비교 및 갱신
        min_move = min([min_move, 2 * i + len(name) - next, i + 2 * (len(name) -next)])
        
    # 알파벳 변경 + 좌우이동 횟수
    answer += min_move
    
    return answer

 

좌우 조이스틱 최소 이동 횟수 계산은 아래 세 가지를 비교해야 합니다.

1. 최소 이동 횟수(name이 'JAN'일 경우, 최소 이동 횟수는 2)

2. 연속된 A가 왼쪽에 있을 경우

3. 연속된 A가 오른쪽에 있을 경우

 

각 문자마다 비교한 후 최소 이동 횟수와 알파벳 변경 횟수를 더하면 정답을 얻을 수 있습니다.