조이스틱 (lv2)
프로그래머스 / 그리디
조이스틱으로 알파벳 이름을 완성하세요. 맨처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동
예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.
- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
제한 사항
- name은 알파벳 대문자로만 이루어져 있습니다.
- name의 길이는 1 이상 20 이하입니다.
크게 봤을 때 '▲▼로 글자를 바꾸는 횟수'와 '◀▶로 글자 자리를 바꾸는 횟수'를 더한 값을 구해야 한다.
▲▼ 이동 횟수는 쉬웠다. 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'문자열을 가진 변수를 선언하고 문자열의 INDEX값이 ▲▼ 이동 횟수 였다. 예외가 있는데 INDEX값 13 보다 큰 수는 아래방향으로 이동 횟수를 계산해야 했고, 26-INDEX 로 해결됬다.
(다른 사람들은 ASCII코드를 활용해 풀더라. 모르면 고생해야지...)
문제는 ◀▶이동 횟수였다. 3가지 경우로 나누어서 생각했다.
첫째, ▶ 이동만 하는 경우
둘째, ◀ 이동만 하는 경우
셋째, ◀▶ 이동을 모두 하는 경우
(세가지 경우를 모두 구해 셋중에 최소값을 구하는 식의 접근)
간편하게 구하기 위해 name에서 'A'가 아닌 알파벳의 INDEX값을 가진 list를 만들었다.
(원하는 문자의 위치로 이동하기 위해 움직여야할 횟수는 INDEX값과 동일하기 때문, ◀이동을 한다고 하면 len(name)-index이다)
이 list를 만들경우 첫번째와 두번째는 매우 쉽게 해결된다. 예를 들면 'AVERAGE'를 list로 만들경우 [1,2,3,5,6]이다.
이때
▶ 이동만 하는 경우는 list 마지막 값인 '6',
◀ 이동만 하는 경우는 len(name)에서 list 첫번째 값인 '1'을 뺀 '6'이다.
여기서 문제는 세번째 경우였다.
이 경우에 list가 [a,b,c,d]일 경우 a를 찍고 반대로 돌아b로 가는 이동 횟수를 b,c의 경우 모두 구해야 한다.
크게 ◀▶이동과 ▶◀이동으로 나뉘는데 list의 첫번째 값이 0인 경우와 아닌 경우가 달랐으며 len(list)가 >1경우와 아닌 경우가 갈렸다. 이 부분에서 어찌저찌 최대한 짧게 짜보긴했지만 코드가 더러워지는 것은 어쩔 수 없었다. 아무튼 아래 처럼 해결했음.
정답2 - 21.05.27
def solution(name):
N = len(name)
alph = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def alphabet(spel):
num = alph.index(spel)
if num > 13:
num = 26-num
return num
updownCount = sum(map(alphabet,[i for i in name]))
# A가 아닌 알파벳들의 index list
_idxList = [i for i,v in enumerate(name) if v != 'A']
if _idxList[0]==0:
_idxList.remove(0)
# 우 이동
right = _idxList[-1]
# 좌 이동
left = N-_idxList[0]
# 좌우우좌
def countlr(index):
return 2*_idxList[index]+N-_idxList[index+1]
if len(_idxList) > 1:
leftright = min(map(countlr, [j for j in range(len(_idxList)-1)]))
_idxList.reverse()
_idxList = list(map(lambda x:N-x, lst))
rightleft = min(map(countlr, [k for k in range(len(_idxList)-1)]))
answer = min(right, left, rightleft, leftright) + updownCount
else:
answer = min(right,left)+updownCount
return answer정답1에 비해 훨씬 짧고 깔끔해짐
한줄 for 문, 사용자정의함수 활용
정답1 - 21.05.25
def solution(name):
N = len(name)
alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
updown = 0
for spel in name:
num = alphabet.index(spel)
if num < 13:
updown += num
else:
updown += (26-num)
i = 1
while i < N:
if name[N-i] != 'A':
break
i +=1
right = N - i
j = 1
while j < N:
if name[j] != 'A':
break
j += 1
left = N - j
lst = []
for i, v in enumerate(name):
if v != 'A':
lst.append(i)
rightleft = 0
if len(lst) > 1 and lst[0] != 0:
k = 0
while k < len(lst) - 1:
move = 2 * lst[k] + N - lst[k + 1]
if rightleft == 0 or move < rightleft:
rightleft = move
k += 1
elif len(lst) > 1 and lst[0] == 0:
l = 1
while l < len(lst) - 1:
move = 2 * lst[l] + N - lst[l + 1]
if rightleft == 0 or move < rightleft:
rightleft = move
l += 1
leftright = 0
if len(lst) > 1 and lst[0] != 0:
k = -1
while -k < len(lst):
move = 2 * (N - lst[k]) + lst[k - 1]
if leftright == 0 or move < leftright:
leftright = move
k -= 1
elif len(lst) > 1 and lst[0] == 0:
k = -1
while -k < len(lst)-1:
move = 2 * (N - lst[k]) + lst[k - 1]
if leftright == 0 or move < leftright:
leftright = move
k -= 1
if leftright>0 and rightleft>0:
mini = min(right, left, leftright,rightleft)
elif leftright == 0 and rightleft>0:
mini = min(right, left, rightleft)
elif rightleft == 0 and leftright >0:
mini = min(right, left, leftright)
else:
mini = min(right,left)
answer = mini + updown
return answer첫풀이...
창피하지만 박제
