[python/탐욕법] 43. 조이스틱(feat. 탐욕법) ★

문제 출처

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

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

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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

 

 

---

나의 코드(실패, 정확성: 36.4)

def solution(name):
    dic = {'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6, 'G':7, 'H':8, 'I':9, 'J':10,
          'K':11, 'L':12, 'M':13, 'N':14, 'O':15, 'P':16, 'Q':17, 'R':18, 'S':19,
          'T':20, 'U':21, 'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26}
    answer = sum(min(dic[name[x]]-1, 27-dic[name[x]]) for x in range(len(name)))
    
    if 'A' not in name:
        return answer + len(name) -1
    
    right_plus, left_plus = 1, 1
    name_ls = list(name)
    name_ls[0] = 'A'
    while name_ls != ['A']*len(name):
        i = 1
        name_ls[i] = 'A'
        right_plus += 1
        i += 1
        
    name_ls = list(name)
    name_ls[0] = 'A'
    while name_ls != ['A']*len(name):
        i = len(name)
        name_ls[i] = 'A'
        left_plus += 1
        i -= 1
    return answer + min(right_plus, left_plus)

😭 여러모로 문제가 많은 코드이니 코멘트를 하지 않겠습니당....

혹시나 보시는 분이 계시다면 밑에 코드를 참고하시길^^....

 

다른 풀이

def solution(name):
    count=0
    alpha='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    d={}  #딕셔너리 생성
    indexes=[]
    current_idx=0
    n=len(name)
    for i in range(len(alpha)):  #1)
        d[alpha[i]]=min(i,26-i)
    #print(d)
    for i in range(n):  #2)
        num=d[name[i]]
        count+=num
        if num !=0 :
            indexes.append(i)  #d의 값이 0이 아닌 것들의 index
    while True:  #3)
        if len(indexes)==0:
            break
        min_dist=99
        min_idx=0
        for it in indexes:
            min_dist2=min(abs(it-current_idx),n-abs(it-current_idx))
            if min_dist2 < min_dist:
                min_dist=min_dist2
                min_idx=it
        count+=min_dist
        indexes.remove(min_idx)
        current_idx = min_idx

    return count

일단 기본적인 개념에 대해서 이야기해보자면, '각 알파벳의 A까지의 거리'와 '첫 번째 위치에서 A가 아닌 알파벳까지의 커서 이동 거리'의 최소값을 더해서 count를 반환해주는 것이다!

나도 이 풀이에서 처럼 '각 알파벳의 A까지의 거리'는 계산하였으나, 두 번째에서 막혀버렸다. '오른쪽으로 커서를 이동하기 시작하면 오른쪽만 갈 것이고, 왼쪽으로 커서를 이동하기 시작하면 왼쪽으로 갈 것이다'라고 내 맘대로 가정을 해 버린 것이 가장 큰 오류였다.

 

1) ABCD~ 각각의 min(i, 26-i)를 저장해주는 dictionary를 for문으로 만들어줬다. min(i, 26-i)는 알파벳 각각의 최소 거리를 계산해주기 위한 것이다.

2) 그 다음 for문에서 모든 알파벳의 A까지의 거리를 카운트해줬다. 여기까지가 앞서 말한 '각 알파벳의 A까지의 거리'가 계산된 것이다. 그리고 num값이 0이 아닌 것들의 index를 indexes에 저장해준다. 이는 그 다음 '첫 번째 위치에서 A가 아닌 알파벳까지의 커서 이동 거리'를 계산해주기 위함이다.

3) 여기서 그리드 알고리즘, 탐욕법 알고리즘의 개념이 사용된다! 가장 먼저 첫 번째 위치에서 A가 아닌 알파벳까지의 최소 거리를 계산해준다. 그리고 최소 거리라고 판단된 알파벳으로 이동한 다음, 또 A가 아닌 알파벳까지의 최소 거리를 계산하여 이동해주는 방식이다. 

 

* 탐욕 알고리즘이란

- 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법

- 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘

- 단! 모든 경우에서 탐욕 알고리즘이 정답인 것은 아니다.