https://school.programmers.co.kr/learn/courses/30/lessons/42860

이 문제 해결의 아이디어는 다른 분의 해설을 참고하여 얻었다.

문제

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)
예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

• 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
• 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
• 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
  따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
제한 사항
name은 알파벳 대문자로만 이루어져 있습니다.
name의 길이는 1 이상 20 이하입니다.

Idea

우선 이 문제를 어느 정도 고민해봤다면, 상하조작은 금방 답을 찾을 수 있었을 것이다. 중요한 해결 과제는 좌우 이동이다...
어떻게 이동해야 이동량을 최소화할 수 있을까?
몇가지 고려사항들부터 뽑아내 보았다.

• 시작 지점에서 좌로 가는 경우와 우로 가는 경우를 고려해 최소한 움직이는 경우를 선택한다.
• 좌,우 이동 시 바꿔야 할 남은 문자가 A뿐이면 더 진행하지 않아도 된다.
• 진행 방향에서 반대 방향으로 한 번 꺾는 경우가 발생할 수 있다.
• 두 번 꺾는 경우는 진행한 만큼 다시 돌아가야하는 것을 고려하면 비효율적이므로 존재하지 않는다.

그래서 시작점에서 n칸만큼 좌로 이동하거나 우로 이동하여 꺾는 경우를 그려보았다.
여기서부턴 친근한 말투로 해볼게요^*^

먼저 아래 그림같이 name이 들어왔다고 해봅시다.

요런 케이스는 좌로갈지 우로갈지만 지정해주는 걸로는 부족하겠죠

그래서 각 지점별로 지정해서 한번씩 꺾어 보는겁니다.
그중 한 경우로 시작점에서 3만큼 우로 진행한 지점을 기준으로 꺾어보겠다라고 한다면 아래와 같겠죠!

그럼 3만큼 우로 갔다가 보이시는 검정원 안의 1번 2번처럼 진행하게 될겁니다
진행 방향대로 표현하면 아래 그림처럼 나오겠죠??

위 그림처럼 이동하다가, 마지막 B지점에 왔다고 해봅시다.
이후에 바꿔야 할 문자가 모두 A밖에 없다면, 굳이 더 이동하지 않아도 되기 때문에 빨간줄처럼 무시할 수도 있을 것입니다!

근데 이건 3만큼 우측으로 나아간 걸 고려한 것이고, 이제 3만큼 좌측으로 나아간 경우도 고려를 해보는 겁니다.
이건 원래 name에서 좌측으로(거꾸로) 3만큼 이동한 지점일 때 보기 편하기 위해 앞 순서부터 문자들을 배치한 겁니다. 원래 name하고 비교해보시면 어떤 표현인지 바로 아실거에요 ~..~

좌측으로 진행했을 때도 우측 때와 마찬가지로 진행할 수 있겠죠!
방문한 지점에서 다시 거꾸로 나아갈 것입니다. 마찬가지로 마지막에 A가 나온다면 모두 지워주면 되겠구요.

이런 방식으로 좌우측 모두 처음부터 name의 절반 부분까지만 나아가며( 반 이상 갔는데 다시 반대로 꺾을 필요는 없으니까요! ) 진행해주면서 최소값이 나올 때를 return 해주는 겁니다

구현

다시 일기체로 돌아갈게요.
위아래로 작동해야할 때는 ord()함수를 이용하였다. ord()함수는 인자로 받은 값(정수나 문자)의 유니코드를 반환을 해준다.
위아래 조작 시 최선의 조작량은 A와 가까운 문자는 A에서 출발한 만큼, Z와 가까운 문자는 Z에서부터 이동한 만큼이 최적값이 되므로 이를 이용해 아래 방식처럼 찾는다.

a_pos = ord('A') # 'A' : 65, 'Z' : 90
z_pos = ord('Z')

cnt = [min(ord(c)-a_pos, (z_pos+1) - ord(c)) for c in n ]

cnt 변수에서 저장되는 list는 전체 코드에서 일부만을 떼와서 n이 뭐지? 하셨을 수도 있지만, 방식만 저렇게 찾아간다는 것을 표현하고 싶었다.
이때 Z부터 가게되면 Z에서 1이므로 Z의 유니코드에서 1을 더한 것에서 빼주도록 한다.

좌우 이동할 때는, name의 절반만큼의 길이에서 각각 좌우로 이동한 경우를 모두 고려해본다.

for i in range(len(name)//2 + 1):
	l_r = name[-i:] + name[:-i] #왼쪽먼저 갔다가 + 오른쪽
    r_l = name[i: :-1] + name[i+1:][::-1] # 기준점에서 빠꾸 + 좌측
    for n in [l_r,r_l]:
    	# 끝에 A들은 셀 필요 없으므로 자르기
        while n and n[-1] == 'A':
        	n = n[:-1]

변수 l_r은 좌측먼저 갔다가 우측으로 가는 경우, r_l은 우측먼저 갔다가 좌측으로 꺾는 경우이다. 이 때 보면 알겠지만 각각의 경우에서 name[-i:]와 name[i::-1]은 꺾고 난 후 밟는 알파벳들이 나오게된다.

좌~우측, 우~좌측의 경우에서 아까 그림처럼 마지막에 나오는 A들은 모두 무시해도 되기 때문에 잘라낸다.

이렇게되면 좌우로의 최적의 이동량은 i만큼 이동한 값과, ( 잘리고난 n의 문자열 길이만큼 이동하므로 ) n의 길이를 더한 것이 되겠다.

# 이렇게 나온 값이 기존의 answer보다 작으면 최소값으로 업데이트할 수 있다.
answer = min(answer, i + (len(cnt)-1) + sum(cnt))

전체 코드

def solution(name):
# 두번 꺽는 경우는 고려하지 않음
    if set(name) == {'A'}:
        return 0
    
    a_pos = ord('A') # 'A' : 65, 'Z' : 90
    z_pos = ord('Z')
    
    answer = float('inf')
    
    for i in range(len(name)//2 + 1):
        l_r = name[-i:] + name[:-i] #왼쪽먼저 갔다가 + 오른쪽
        r_l = name[i: :-1] + name[i+1:][::-1] # 기준점에서 빠꾸 + 좌측
        for n in [l_r,r_l]:
            # 끝에 A들은 셀 필요 없으므로 자르기
            while n and n[-1] == 'A':
                n = n[:-1]
            cnt = [min(ord(c)-a_pos, (z_pos+1) - ord(c)) for c in n ]
            answer = min(answer, i + (len(cnt)-1) + sum(cnt))

    return answer

while문 이후로는 좌우측 각각의 경우에서 상,하로 이동한 값을 계산한 후 List로 저장하여 마지막에 한번에 더하면 상,하로의 최적의 이동량을 구할 수 있을 것이다.

마지막에 최소값을 업데이트할 때, (len(cnt)-1)이 되는 이유는 꺾는 순간 꺾는지점까지 포함이 되어 있기 때문이다. i부터 고려 안했으면 빼지 않아도 되겠다.