프로그래머스(programmers) 조이스틱 python 정답 [Greedy Algorithm]

프로그래머스(programmers) 조이스틱 python 정답 [Greedy Algorithm]

문제 링크

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

프로그래머스

---

문제 정답

입출력 예

def solution(name):

	# 조이스틱 조작 횟수 
    answer = 0
    
    # 기본 최소 좌우이동 횟수는 길이 - 1
    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
                    
        # 왼쪽으로 쭉 진행 
        # 왼쪽으로 진행하다가 오른쪽으로 턴
        # 오른쪽에서 진행하다 왼쪽으로 턴
        min_move = min(min_move, 2 *i + len(name) - next, i + 2 * (len(name) -next))
        
    # 알파벳 변경(상하이동) 횟수에 좌우이동 횟수 추가
    answer += min_move
    return answer

---

문제 해설

아이디어 : 모든 정점에서 A가 아닌 알파벳을 모두 처리하며 이동할 때의 최소값을 구한다.

 

각 칸에서 바꾸는 최소값은 위로 올리거나 아래로 내리거나 해서 (A->Z or Z->A) 그 최소값을 구하면 된다.

후자의 경우 A->Z로 바꾸는 +1을 더해준다.

 

그러면 칸 간의 이동의 최소값은 어떻게 구하는가?

일단 i만큼 왼쪽에서 오른쪽으로 이동했다고 가정해보자.

그 다음 i에서 오른쪽으로 가장 가까운 A가 아닌 알파벳의 좌표 next를 구한다.

그러면 앞뒤뒤 혹은 뒤앞앞으로 진행하면 i와 next 사이의 모든 알파벳은 처리되었다 생각할 수 있다.

i에서 오른쪽으로 이동할 때 i와 next 사이에는 A가 아닌 알파벳이 없기 때문이다.

 

즉 i에서 오른쪽으로 가장 가까운 next좌표를 구하고, i와 next 사이를 왼쪽에서 처리할 때 빠른지, 오른쪽에서 처리할 때 빠른지를 매 좌표에서 갱신한다.

next가 없을 경우 앞뒤뒤, 뒤뒤앞의 최소값은 i다. 물론 이는 이 전에 이미 갱신되었을 수도 있다.

원으로 따지면 이런 식으로 이동... 발 그림 ㅈㅅ

그 거리의 최소값을 구하면 된다.

만약 다음 알파벳이 없으면 next가 n이 되기 때문에 좌우 이동 최소값은 i가 될 것이다(by 오른쪽)

물론 이 값이 이전 최소값보다 클 수 있기 때문에 알아서 갱신될 것이다

이 부분의 구현이 바로 아래 라인이다.

        min_move = min(min_move, 2 *i + len(name) - next, i + 2 * (len(name) -next))

최적화 예시는 다음과 같다.

AEAAAAAAE (n=9)

• 첫번째 0 + 0 + 8,  0 + 2*8
• 두번째 1 + 1 + 1, 1 + 2*7 (여기서 최소값 3)
• 세번째  2+ 2+ 1, 3 + 2*6
• ....
• 마지막 -1 : 8+8+1,  8 + 2*1
• 마지막 9 + 9 + 0, 0

쉬운 문제는 아니었던것 같다.