내가 이 문제를 풀었던 생각의 흐름은 다음과 같다. 각 위치에서 위아래로 조이스틱을 이동하는 것과 좌우로 이동하는 것 두 가지 경우가 있을 것 이고, 각 각은 독립적이라는 것. 즉, 위아래로 이동하는 것의 최솟값 구하고, 좌우로 이동하는 것의 최솟값을 구해서 두 값으 더하자였다.
위아래 이동의 최솟값을 구하는 것은 어렵지 않았다. 타겟 문자가 H라고 한다면 A부터 H까지 차례로 움직이는 것과 A부터 뒤로 H까지 이동하는 것 두 가지 경우 중 최소의 것을 택하면 된다.
문제는 좌우로 이동하는 것의 최솟값을 구하는 것이었다. 해당 부분은 생각하는 데 조금 애를 먹었다. 나는 내 풀이가 그리디 보다는 완전 탐색에 가깝다고 생각한다.
보통 다른 분들의 풀이를 보면 생각의 흐름이 현재 위치(현재 상황)에서 오른쪽으로 가는 것과 왼쪽으로 가는 것 중 최소가 되는 것(탐욕적인 선택)을 반복하기 때문에 그리디라고 생각해서 풀고 있다. 나는 이 사고가 이 문제를 푸는 데 조금 어렵게 하는 것 같았다.
그래서 내가 푼 방식은 완전 탐색으로 접근했는데, 현재 위치를 i 번째 인덱스라고 한다면, 그 i 번째 위치가 오른쪽으로 이동하고 왼쪽으로 쭉 이동하는 것이었다. 이 때 중요한 것은 어디까지 이동할 것인가 인데 이것은 연속된 A까지로 했다.
그림으로 표현하면 다음과 같다. 1,2,3은 순서이다.
모든 경우의 수를 커버할 수 있을려면, 현재 위치에서 빨간색으로 이동한 순서대로 이동하는 것과 파란색으로 이동한 순서를 비교하는 것이다.
해당 비교를 각 인덱스 위치에서 비교해주면 오른쪽왼쪽으로 이동하는 최소값을 구할 수 있다.
그리고 점선으로 표시한 부분은 현재 위치에서 연속하는 최대 A의 위치이다. 여기까지 이동하는 걸 말로 표현하기는 조금 힘들 것 같다. 느낌상 뭔가 당연히 연속한 최대 A까지 검사해야할 것 같지 않은가 싶었다.
def solution(name):
answer = 0
length = len(name)
name = list(name)
UpDown = sum([ min(ord(n)-ord('A'),26-(ord(n)-ord('A'))) for n in name ])
LeftRight = length - 1
for i in range(length):
# 연속한 A위치 구하기
index = i + 1
while index < length and name[index] == 'A':
index = index + 1
LeftRight = min(LeftRight, i * 2 + length - index)
LeftRight = min(LeftRight, (length - index) * 2 + i)
answer = UpDown + LeftRight
return answer
