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

Lv2가 맞나 싶은 난이도... 문제에 대한 감이 어느정도 있어야 이게 그리디로 푸는게 맞는지 아닌지 아는 것 같다.

 

문제

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

 

접근 방법

크게 상하 / 좌우로 움직일 때로 나뉜다. 

상하 이동 : 알파벳 바꿀 때 (어차피 A인 경우에는 0이므로 그냥 계산해주면 됨)
1) N(78) 이전 문자로 변경 시 위로 이동 -> 이동횟수 = 해당문자아스키값 - 65(A)
2) 이외에는 아래로 이동 -> 이동횟수 = 90(Z) - 해당문자아스키값 + 1 (+1은 A->Z 변경)
-> 더 작은 값으로 설정하기

* 여기에서 ord() 메서드를 사용해주면 해당 문자의 아스키값을 리턴해준다

좌우 이동 ** 풀이 참고 **
- 기본 최소 이동 횟수 : 길이 -1
- 연속되는 A가 있을 때, 그것의 왼쪽이나 오른쪽부터 시작하며 알파벳을 변경하는 것이 가장 효율적
(기존, 연속A의 왼쪽에서 시작, 연속A의 오른쪽에서 시작) 중 min값이 답
- 연속되는 A가 있는 곳에는 굳이 갈 필요 없음, 그 부분을 제외하고 수정하는 경우 계산
- 다만 연속되는 A가 여러 개인 경우, 가장 긴 부분을 안 가는 것이 효율적임

 

여기가 도저히 이해가 안되서 블로그를 많이 뒤져봤다 보니까 원래는 왼쪽만 계산해줘도 됬는데, 2022년 기준 테스트케이스가 추가되어 오른쪽을 계산하는(뒤에서 시작하는) 부분이 추가되어야 한다고 한다. 이해를 돕기 위해 이미지를 하나 첨부한다.

좌우 이동 min값이 될 수 있는 경우 3가지

 

 

코드

# 2022-04-06
# 프로그래머스 고득점 kit 그리디 - 조이스틱 
# https://programmers.co.kr/learn/courses/30/lessons/42860

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

 

2022.4.6 테케 기준 통과했다