[programmers] Greedy - 조이스틱

문제

programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱

 

풀이

속을 많이 썩인 문제였다. 해당 문제도 조건이 다양한 문제로, 문제에 제시되어 있긴 하지만, 조건이 다양하면 그리디를 사용해 보면 좋다는 생각을 갖고, 조건을 정리하면서, 세 가지 경우 중 최솟값을 구하면 된다는 생각이 들었다.

1. 조이스틱으로 오른쪽으로 쭉 가는 경우
2. 조이스틱으로 왼쪽으로 쭉 가는 경우
3. 조이스틱으로 오른쪽으로 가다가 왼쪽으로 가는 경우

해당 3가지 경우를 제외하고는 없기 때문에, 셋 중 최소인 값을 구해주면 좌우로 이동하는 횟수가 계산된다.

그리고, 위아래로 움직여야 하는 경우를 계산해야 하는데, 위아래로 움직이는 경우는 각 문자마다 위로 움직이는 경우, 아래로 움직이는 경우 중 작은 값을 이용하면 된다. 해당 값을 계산하기 위해, 알파벳 문자열을 선언한 뒤, 해당 인덱스까지 가기 위해 위로 눌러야하는 횟수와 아래로 눌러야 하는 횟수를 계산하여 둘 중 작은 값을 더해주었다.

해당 문제는 좌우로 움직이는 경우의 수 중 3번째 경우를 고려하지 않고 풀이를 진행하면서 막혔었는데, 갔다가 다시 오는 경우도 있다는 것을 판단하는 게 조금 어려울 수 있다. 하지만 해당 경우를 파악한다면 금방 풀 수 있는 문제로, 갔다 오는 경우 A가 가장 많은 위치에서 전진하는 방향을 돌려야 하기 때문에, A가 가장 많은 위치를 찾아서 돌려 주었다.

 

코드

def solution(name):
    answer = 0
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    
    for i in name:
        answer += min(alphabet.index(i), 26-alphabet.index(i))
        
    mov1 = len(name.rstrip("A")) - 1    # 앞으로만 가는경우
    mov2 = len(name.lstrip("A"))        # 뒤로만 가는경우
    
    idx = 0
    n = 1
    while True:
        tmp = name.find("A"*n)
        if tmp == -1:
            break
        idx = tmp
        n += 1                      # A가 가장 많은 곳 위치 찾기
        
    mov3 = 1000000000000
    
    if idx != 0 and idx != len(name.rstrip("A"))-1:
        # A가 가장 많은 곳이 맨앞 또는 맨 뒤쪽인 경우 배제
        mov3 = (idx-1)*2 + len(name) - (idx + n - 1)    
        # A가 가장 많은 곳을 기준으로 갔다가 돌아오는 경우
        
    answer += min(mov1, mov2, mov3)
    
    return answer