[프로그래머스] Greedy 문제 - 조이스틱

문제 : n개의 A로 이루어진 문자열을 조이스틱으로 상하좌우 이동하며 주어진 이름을 만드는 최소 횟수를 구하시오. (단 첫번째에서 왼쪽으로 움직이면 맨 오른쪽으로, A에서 위로 움직이면 Z로 이동)

 

def solution(name):
    answer = 0
    n = len(name)
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    updown_count = [0 for _ in range(n)] #알파벳 맞추는 게 어느 방향이 더 빠를지

    #알파벳 맞추는 최소 이동 횟수 정하기
    for idx, letter in enumerate(name):
        if alphabet.find(letter) > len(alphabet) - alphabet.find(letter):
            updown_count[idx] = len(alphabet)-alphabet.find(letter)
        else:
            updown_count[idx] = alphabet.find(letter)

    #print(updown_count)

    nonzero_point = [idx for idx, v in enumerate(updown_count) if v != 0]


    if len(nonzero_point) == len(name): #0이 아닌 포인트 없음
        answer += len(name) - 1

    else:
        index = 0
        while len(nonzero_point):
            #print(nonzero_point)
            len_non = len(nonzero_point)
            len_for_first = min(abs(nonzero_point[0] - index), abs(len(name) - nonzero_point[0])) #첫번째 점까지 거리
            len_for_last = min(abs(nonzero_point[len_non-1] - index), abs(len(name) - nonzero_point[len_non-1] + index)) #마지막 점까지 거리            
            if len_for_first > len_for_last:
                index = nonzero_point[len_non-1]
                answer += len_for_last
            else:
                index = nonzero_point[0]
                answer += len_for_first
            #print(len_for_first, len_for_last, index)
            nonzero_point.remove(index)

    answer += sum(updown_count)
    return answer

어후;;;; 문제 보기보다 엄청 어렵네요. 예상보다 생각해줘야 하는 테스트 케이스들도 많고... 한번에 통과하기는 쉽지 않은 타입의 문제였습니다.

포인트는

1. index = 0 를 설정
2. index를 기준으로 첫번째와 마지막 non-A 위치까지 이동하는 왼쪽 이동횟수, 오른쪽 이동 횟수를 각각 구함. 첫번째 왼쪽 횟수, 첫번째 오른쪽 횟수, 마지막 왼쪽 횟수, 마지막 오른쪽 횟수 총 4개의 거리
3. 1의 4개 중에서 가장 짧은 것을 고르고 result에 이동 횟수 추가, index는 가장 짧은 거리로 갈 수 있는 첫번째 또는 마지막 위치로 갱신하고 해당 위치를 non-A에서 제거(여기서 세로 이동 횟수를 더해 이동 횟수를 0으로 만들어도 될듯)
4. 2-3를 반복하며 더이상 non-A가 없을 때까지 반복

인데 말하면서도 어렵네요 ㅋㅋ...