💡 문제 해결 아이디어

🛠 피드백

• Greedy보다는 Brute Force에 가까운 듯한 문제.
• 다른 사람의 코드를 참조한 정답
• 기본 최소 이동 횟수는 길이 - 1
• 연속되는 A가 있을 때, 그것의 왼쪽이나 오른쪽부터 시작하며 알파벳을 변경하는 것이 가장 효율적이다.
• 때문에 (기존, 왼쪽부터 시작, 오른쪽부터 시작) 중에서 minimum이 답이다.

내가 생각한 아이디어

• 연속되는 A의 최대 길이가 핵심포인트.
• 연속되는 A가 있는 곳에는 굳이 갈 필요가 없으므로, 그 부분을 제외하고 수정하는 경우를 계산한다.
• 다만, 연속되는 A가 여러군데인 경우 가장 긴 부분을안가는게 더 효율적일 것이다. ex) JAAJAAAAJ 인 경우 4번째 J를 처리하기 위해서 2, 3번째의 연속된 AA를 건너는게 5,6,7,8번쨰의 연속된 AAAA를 건너는 것 보다 낫다.

💻 작성된 코드

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
            
        # 기존, 연속된 A의 왼쪽시작 방식, 연속된 A의 오른쪽시작 방식 비교 및 갱신
        min_move = min([min_move, 2 *i + len(name) - next, i + 2 * (len(name) -next)])
        
    # 알파벳 변경(상하이동) 횟수에 좌우이동 횟수 추가
    answer += min_move
    return answer

🙌추가 설명

연속된 A의 왼쪽 시작 방식이라는 것은 아래 그림 중 첫번째 그림처럼

말 그대로 연속된 A의 왼쪽으로 커서를 먼저 이동한 후 (오른쪽으로 가는 화살표), 하나씩 알파벳을 바꿔가면서 연속된 A의 오른쪽으로 이동하는 것입니다. (왼쪽으로 가는 화살표)

때문에, 연속된 A들의 왼쪽 부분을 두 번 지나가는 셈이기 때문에 2 * i 를 하고, 오른쪽 부분 len(name) - next을 더한 것입니다.

반대로 연속된 A의 오른쪽 시작 방식이라는 것은 아래 그림 중 2번째 그림처럼

연속된 A의 오른쪽으로 커서를 먼저 이동한 후 (왼쪽으로 가는 화살표), 하나씩 알파벳을 변경하며 연속된 A의 왼쪽으로 이동하는 것입니다. (오른쪽으로 가는 화살표)

해서 연속된 A들의 오른쪽 부분을 두번 지나가기 때문에 2 * (len(name - next))를 하고, 연속된 A의 왼쪽 부분 i를 더한 것 입니다!

위 그림 중 첫번째처럼 연속된 A의 왼쪽 부분이 더 짧은 경우에는 왼쪽을 두번 지나가는게 더 횟수가 적고,

두번째처럼 연속된 A의 오른쪽 부분이 더 짧은 경우에는 오른쪽을 두번 지나가는게 더 횟수가 적은 경우입니다!

또한, 연속된 A가 여러개 있는 경우도 있을 수 있으니 (ex. BCAABCDAAAAAAD) for을 통해 반복하며 제일 긴 연속된 A를 찾는 구조입니다.