[프로그래머스/python] 탐욕법(Greedy) : 조이스틱

문제

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

• ▲ - 다음 알파벳
• ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
• ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
• ▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

• 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
• 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
• 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
• 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

 

정답

def solution(name):
    name = list(name)
    answer = 0
    i = 0
 
    while 1:
        left = 1
        right = 1
        # 알파벳 바꾸기
        if name[i] != 'A':
            answer += min(ord(name[i])-ord('A'),ord('Z')-ord(name[i])+1)
        name[i] = 'A'

        # 위치 바꾸기
        if name == ['A']*len(name):
            break
        else:
            for k in range(1, len(name)):
                if name[i + k] == "A":
                    right += 1
                else:
                    break
                if name[i - k] == "A":
                    left += 1
                else:
                    break
                
            if right > left:
                answer += left
                i -= left
            else:
                answer += right
                i += right

    return answer

---

# 알파벳 바꾸기
        if name[i] != 'A':
            answer += min(ord(name[i])-ord('A'),ord('Z')-ord(name[i])+1)
        name[i] = 'A'

각 자리의 알파벳을 만들기 위해 ▲버튼을 이용하는게 빠른지 ▼버튼을 이용하는게 빠른지 확인한 후 

더 적은 수를 answer에 더해준 후 해당 알파벳을 "A"로 바꾼다. 

 

if name == ['A']*len(name):
            break
        else:
            for k in range(1, len(name)):
                if name[i + k] == "A":
                    right += 1
                else:
                    break
                if name[i - k] == "A":
                    left += 1
                else:
                    break

name의 모든 알파벳이 A가 되었다는 뜻은 모든 알파벳을 다 확인했다는 뜻이므로 break로 빠져나온다.

그렇지 않다면 현재있는 위치에서 앞 또는 뒤의 알파벳이 A가 아닐 때까지 이동하여

앞으로 이동한 값은 right에, 뒤로 이동한 값은 left에 저장한다.

 

 if right > left:
                answer += left
                i -= left
            else:
                answer += right
                i += right

right랑 left랑 비교하여 더 가까운 쪽에 있는 알파벳으로 이동한다.

answer에는 앞 또는 뒤로 이동한 값인 right 또는 left 값을 더해주고

알파벳의 위치를 가리킬 i를 이동한만큼 더하거나 빼준다.