프로그래머스_조이스틱

1. 문제

출처 : 프로그래머스

2. 소스코드

cntlist = [1000000000]    #이름을 완성했을 때 횟수를 저장하는 배열 ## 'A'부터 올려가며/내려가며 문자로의 조작횟수 비교, 작은 것 선택 def count(name, idx):     return min(ord(name[idx])-ord('A'), ord('Z')-ord(name[idx])+1)   ## 조이스틱 def Joystick(name, naming, idx, cnt, rlcnt, rl):     if rlcnt == len(name): return    # 좌우 조작횟수가 이름의 길이가 되면 불필요한 좌우이동 -> 리턴     if cnt >= min(cntlist): return    # 현재 cnt보다 적은 횟수로 이름을 완성할 수 있다면 이후 계산이 불필요 -> 리턴     if name[idx]!=naming[idx]:          cnt += count(name, idx)    # 문자변경 조작횟수 count          naming = naming[:idx] + name[idx] + naming[idx+1:]    # idx의 문자만 고침     #print('naming= ', naming, '\tcnt= ', cnt, '\t',rl)    # for debug         if naming == name:    # naming과 name이 같다면 (이름 완성)         cntlist.append(cnt)    # 현재 조작횟수 저장         return     ## 오른쪽으로 이동     if idx+1 == len(name):    # 인덱스 바깥 처리        Joystick(name, naming, 0, cnt+1, rlcnt+1, rl+'오')     elif idx+1 < len(name):        Joystick(name, naming, idx+1, cnt+1, rlcnt+1, rl+'오')      ## 왼쪽으로 이동     if idx-1 < 0:    # 인덱스 바깥 처리        Joystick(name, naming, len(name)-1, cnt+1, rlcnt+1, rl+'왼')     elif idx-1 >= 0 :        Joystick(name, naming, idx-1, cnt+1, rlcnt+1, rl+'왼')     return     def solution(name):     answer = 0     idx = 1     # name의 길이만큼 'A'인 문자열을 가지고 조이스틱 조작 시작     Joystick(name, 'A' * len(name), 0, 0, 0, '')     return min(cntlist)

 

3. 고찰

1) 변수 설명

cntlist : 여러 방법으로 이름이 완성될 수 있다. 오른쪽으로 쭉 완성시킬 수도, 왼쪽으로 쭉 완성시킬 수도, 왼오 번갈아가며 완성시키는 방법도 있다. 이때 여러 방법 중 가장 최소 cnt를 찾아야 하므로 전역변수를 이용해서 cnt를 추가하였다. 최종 답은 cntlist의 최소값을 리턴한다.

name : 최종 완성해야하는 이름. 문제에서 주어진다. ex) JEROEN

naming : 현재 만들어가고 있는 이름. ex) JAAAAA, JAAAAN, JAAAEN 등

idx : 현재 내가 건드릴 인덱스

cnt : 현재까지 조이스틱 조작 횟수

rlcnt : 현재까지 좌우 조이스틱 조작 횟수

rl : 디버깅을 위해 오른쪽으로 이동하면 '오', 왼쪽으로 이동하면 '왼'을 추가하여 확인하였다.

 

2) 알고리즘

Joystick 재귀함수를 구현하였다.

종료조건 1) 좌우 조작횟수가 이름의 길이와 같은 경우. 이 경우엔 불필요한 좌우이동이 포함되어 있으므로 리턴

            2) 현재 cnt보다 적은 횟수로 이름을 완성할 수 있는 경우. 굳이 큰 cnt까지 계산할 필요는 없으므로 리턴

            3) 이름을 완성한 경우. cntlist에 현재 cnt를 추가하고 리턴한다.

현재 idx에 해당하는 문자를 변경해주고 그만큼의 조작횟수를 count하여 cnt에 더해준다.

오른쪽 또는 왼쪽으로 이동하여 반복한다. 이때 cnt+1, rlcnt+1 해준다.