진짜 열심히 풀었는데.... 반이나 계속 안됨...
일단 내가 파악한 것은 A 가 연속으로 나올 때가 관건인 문제였다. 내가 짰던 알고맂므의 문제는, 문제에서 주는 JAZ 같은 케이스에서 1 정도 더 큰 답이 나온 다는 거였다. 테스트에 대한 케이스를 더 나눠서는 일반화가 불가능 할 것 같아서 다른 사람 풀이를 참고해서 풀었다. 일단 중간에 한번 테스트 케이스가 바뀌어서 그런지 찾아도 안되는 답이 굉장히 많았다...
그래서 여기 에서 참고했는데,
이런 알고리즘을 따르고 있다!!! 내가 코드를 길고 험난하게 짜긴 했지만 2번째 케이스까지는 고려를 했는데 3번재 케이스를 고려를 못해서 정답이 안나왔다는 것을 알 수 있었다.
def solution(name):
answer = 0
# 정방향(좌->우)으로 움직이면 (길이 - 1) 회 움직임.
min_move = len(name) - 1
for i, c in enumerate(name):
# 알파벳 변경 : 상하 이동
answer += min(ord(c) - ord('A'), ord('Z') - ord(c) + 1)
# 해당 자리 다음에 A가 연속되는 문자열이 있다면 그 길이가 얼마인지 계산.
next = i + 1
while next < len(name) and name[next] == 'A':
next += 1
# 기존, 연속 A 왼쪽에서 접근해서 좌->우->좌 로 꺾을지, 연속 A 오른쪽에서 접근해서 우->좌->우 로 꺾을지
# 여기에 min_move 가 들어가는 이유는, 현재까지 제일 작은거랑 새로운 두개의 루트 중 최소를 찾아야 하기 때문.
min_move = min([min_move, 2 * i + len(name) - next : , i + 2 * (len(name) -next)])
# 결과 : 알파벳 변경 + 좌우이동
answer += min_move
return answer
참고