[프로그래머스][Level2] 조이스틱 (파이썬)

---

문제출처

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

프로그래머스

---

문제를 스스로 해결하였는가?  ->  X

 풀이 아이디어가 떠오르지 않았던 문제. 구글링해서 솔루션을 찾아보니 아이디어가 신박(?)해서 정리해두려고 한다. 근데 솔루션보고 이게 왜 그리디 문제이지? 싶었는데 테스트케이스가 추가되서 그리디로 풀면 실패뜨고 브루트포스로 구현해야한다고 한다. 무튼 소스코드에서 내가 새로 작성한 부분은 없다.

---

필요한 배경 지식

• 브루트포스

---

아이디어

• 조이스틱을 상하로 움직이는 횟수는 좌우 움직임과 상관없이 항상 고정되어 있다.
• A로만 이루어진 가장 긴 문자열을 지나지 않아야 좌우 조이스틱 움직임을 최소로 할 수 있다.
• 연속된 A의 왼쪽을 두 번 오른쪽을 한번 거치는 방법과 오른쪽을 두 번 왼쪽을 한 번 거치는 방법 중 작은 값을 선택.

---

전체코드

 어차피 name의 모든 문자에 대해 반복문을 진행하니 일반성을 잃지 않고 구간 (i, next)를 'A'로만 이루어진 가장 긴 문자열이라고 생각할 수 있다. 다음으로 구간 (i, next)의 왼쪽을 두 번 거치는 방법과 오른쪽을 두번 거치는 방법 중 작은 것을 선택한다.

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)
        next = i + 1
        # 연속된 A구간 찾기, 구간 (i, next) 에는 연속된 A값들만 존재함
        while next < len(name) and name[next] == 'A':
            next += 1
        min_move = min([min_move, 					# 기존에 저장된 최소값
                        2 *i + len(name) - next, 	# (i, next)에서 왼쪽을 두 번 탐색
                        i + 2 * (len(name) -next)]) # (i, next)에서 오른쪽을 두 번 탐색
    answer += min_move
    return answer​