문제 설명
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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 |
풀이 - 실패
def get_alphabet_count(c):
next_alphabet = "ABCDEFGHIJKLMN"
prev_alphabet = "ZYXWVUTSRQPO"
if ord(c) - ord('A') < 14:
return next_alphabet.find(c)
else:
return prev_alphabet.find(c) + 1
def solution(name):
name = [get_alphabet_count(c) for c in name]
idx = answer = 0
while True:
answer += name[idx]
name[idx] = 0
if not sum(name):
return answer
left = right = 1
while not name[idx - left]:
left += 1
while not name[idx + right]:
right += 1
if name[idx - left] + left < name[idx + right] + right:
answer += left
idx += -left
else:
answer += right
idx += right접근
자신이 위치한 곳에 해당하는 알파벳으로 바꾸기 위해 'A'에서 얼만큼 이동할지를 계산하는 것부터 고민했다.
그래서 공책에 'A' ~ 'Z'까지 적고, ▲와 ▼를 눌렀을 때 얼만큼의 이동을 필요로 하는지 적었다.
그랬더니 'N'은 ▲, ▼ 상관없이 13번의 이동을 필요로 한다. 'N'보다 이전에 있는 알파벳은 ▲로 변경하는 것이 효율적이고, 'N' 다음에 있는 알파벳은 ▼로 변경하는 것이 효율적이라는 것을 알았다.
문제는 현재 index를 어디로 이동할지를 결정하는 것인데, 당연히 해당 index의 알파벳을 변경하는데 드는 비용 + 해당 index까지의 이동 비용의 값이 작은 쪽을 선택해서 이동시키면 문제를 풀 수 있을 것이라 생각했다.
다른 사람의 풀이
그러나 그것은 잘못된 풀이 방법이었다. 적어도 해당 방법으로 푼다면 테스트케이스가 잘못 나오는 것을 바로 확인할 수 있다.
if left < right:그래서 인터넷을 통해 검색을 해 봤더니 비슷한 풀이가 여러 개 나왔고, 그 풀이들과 내 풀이의 차이점을 찾아보니 조건문 하나만 다를 뿐이었다.
이 풀이를 보고 내가 생각한 풀이가 왜 틀렸을까를 생각해보니 'A' 때문이었다. 'A'는 변경할 필요가 없기 때문에 이쪽으로 이동하면 불필요한 이동을 한 셈이 된다.
하지만, 내가 접근한 풀이는 'A'의 값이 0이 되기 때문에 가장 작은 값으로 인식되어 'A' 쪽으로 이동하게 된다. 그래서 불필요한 이동이 추가되어 최적의 선택을 할 수 없던 것이다.
일단 이 문제에 있어서 우선순위는 바로 '좌우 이동 횟수'라는 것을 깨달았다.
