[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 조이스틱 (python)

풀이

def solution(name):
    answer = 0

    minMove = len(name) - 1

    for i, char in enumerate(name):

        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)

        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1

        minMove = min([minMove, 2 * i + len(name) - next, i + 2 * (len(name) - next)])
  
    answer += minMove

    return answer

모범답안 참고

• 연속된 A를 찾고 이에 따른 최소 이동 길이를 찾으면 된다.
• enumerate를 사용하면 index와 배열 안의 요소를 한 번에 사용할 수 있다.
• ord(문자)를 사용하면 해당 문자의 아스키 코드를 알 수 있다.
• while문 내에서 해당 문자가 A인 경우 연속된 A를 찾고 이에 따라 minMove를 갱신한다.
• 가장 긴 연속된 A를 찾는 조건문도 추가하여 가장 길 때만 minMove를 갱신하도록 했는데, 그렇게 하니까 테스트 케이스 하나가 실패했다. 그래서 매번 minMove를 갱신하도록 수정했다.

# 코드 설명 : 연속된 A에 따른 최소 이동 길이

minMove = min([minMove, 2 * i + len(name) - next, i + 2 * (len(name) - next)])

• minMove 초기값 = len(name) - 1 : 조이스틱이 움직일 수 있는 가장 최대값을 의미한다.
• 2 * i + len(name) - next : 맨 앞에서 시작해서 연속된 A의 시작점까지 갔다가 뒤쪽으로 이동 후, 연속된 A의 끝점까지 이동.

• i + 2 * (len(name) - next) : 뒤쪽부터 시작해서 연속된 A의 끝점까지 갔다가 다시 앞으로 이동 후, 연속된 A의 시작점까지 이동.

테스트 케이스

name	return
AAAA	0
AAAB	2
BBBBAAAABA	12

 

마지막 테스트 케이스에서 애먹었다. 조이스틱 방향 트는 걸 한 번만 할 수 있다고 착각해서 13으로 답을 냈었는데 그게 아니었다...

어려움