[99클럽 코테 스터디 16일차 TIL] 프로그래머스 | Greedy 조이스틱

16일차 Greedy

 

Problem

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

프로그래머스

 

 

Sol

상하좌우 조이스틱을 움직여서 주어진 알파벳 이름을 완성하기 위해 필요한 최소한의 조작 횟수를 구하는 문제

위, 아래로 움직여서 알파벳을 변경하고, 좌, 우로 커서를 이동하여 완성

 

Greedy Algorithm

 

 

 

 

 

 

---

✔ Answer

def solution(name):
    # 알파벳 리스트
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    n = len(name)
    min_move = n - 1  # 초기 커서 이동 횟수 (한쪽 방향으로 쭉 이동하는 경우)
    answer = 0
    
    for i in range(n):
        # 현재 문자가 'A'에서 몇 번째 떨어져 있는지 계산
        index = alphabet.index(name[i])
        # 위 또는 아래 방향으로 알파벳을 맞추는 최소 조작 횟수
        answer += min(index, 26 - index)
        
        # 다음 위치부터 연속된 A의 끝 위치 찾기
        next_idx = i + 1
        while next_idx < n and name[next_idx] == 'A':
            next_idx += 1
        
        # 커서를 좌우로 이동하는 최소 이동 횟수 계산
        min_move = min(min_move, i + i + n - next_idx, 2 * (n - next_idx) + i)
    
    answer += min_move
    return answer

---

💬 조금 해이해지는 것 같은데 더 열심히 해야겠습니다. 자료 구조 공부, 알고리즘 공부 함께 병행 고고티비