[탐욕법(Greedy)] 조이스틱

# Problem

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

 

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

▲ - 다음 알파벳

▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)

◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)

▶ - 커서를 오른쪽으로 이동

 

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

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.

- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.

- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.

따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

 

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

 

제한 사항

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

입출력 예

name	return
"JEROEN"	56
"JAN"	23

 

# My Answer

def solution(name):
    no = [0 for _ in range(len(name))]
    idx=[]
    
    #1 - 'A'가 아닌 알파벳들 만들 때 클릭수 카운트
    for i,c in enumerate(name):
        if c!='A':
            no[i]=min(ord(c)-ord('A'),ord('Z')-ord(c)+1)
            
    #2 - 'A'가 아닌 알파벳들의 인덱스        
    for i in range(0,len(no)):
        if no[i]!=0:
            idx.append(i)
    
    #3 - 옆으로 이동수 최소값 찾기 
    m = len(name)-idx[0] # 모두 역방향으로 이동할 때 이동수
    for i in range(len(idx)-1):
        m = min(m,2*idx[i]+len(name)-idx[i+1])
    
    #4 - 알파벳 만드는 클릭 수 + 옆으로 이동하는 수의 최소값
    if len(idx)==len(name):
        return sum(no)+len(no)-1
    else:
        return sum(no)+m

 

#1 - 'A'가 아닌 알파벳들 만들 때 클릭수 카운트

         - 'A'부터 세는 경우와 거꾸로 'Z'부터 세는 경우 중 작은 값

         - "JAZ"의 경우 J를 만드려면 9번, Z를 만드려면 거꾸로 1번 

 

#2 - 'A'가 아닌 알파벳들의 인덱스

         - 리스트 idx 는 'A'가 아닌 값들의 인덱스 ( 'A'가 아닌 값들은 클릭수 세야하므로)

         - "JAZ"의 경우 idx = [0,2]
 

#3 - 옆으로 이동수 최소값 찾기 

          m = len(name)-idx[0] # 초기값은 모두 역방향으로만 이동했을 때의 이동수

         - idx의 인덱스들 중 처음부터 정방향으로만 가는 경우, 첫번째 문자만 정방향, 나머진 역방향으로 계산하는 경우....를 모든 인덱스에 대해 계산하고 그 중 최소값

         - "JAZ"의 경우 앞에서 부터 정방향으로만 이동하는 경우는 이동수 2, 역방향으로 이동하는 경우는 1로 최소값은 1이다.

         - "ABAACAD" 의 경우 

              idx = [1,4,6]

              B만 정방향, C,D 역방향 - > 2*(B까지 이동수) + ( B 다음 A가 아닌 수인 C까지 이동수) = 2*1 + 3 = 5

                                                         - 다시 0으로 돌아가서 역방향으로 가야하므로 2를 곱해준다

                                                         - 역방향 한번에 이동한다고 생각해도 되니까 제일 먼 거리 하나만 더하면 된다. 

              B,C 정방향, D는 역방향 = 2*4 + 1 = 9

              B,C,D 모두 정방향 = 6

              B,C,D 모두 역방향 = 6

              최소값은 5

 #4 - 알파벳 만드는 클릭 수 + 옆으로 이동하는 수의 최소값