조이스틱

문제

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

문제를 보고 든 생각

내가 이걸 할 수 있을까라는 생각이 들었다.

가면 갈수록 내가 풀 수 있는 문제가 사라지는 기분이다.

나의 아이디어

조이스틱을 상하로 움직여서 최소 횟수로 스펠링을 바꾸는 법은 알겠으나

좌우로 움직이는 경우에서 최소 횟수를 구하는 방법이 떠오르지 않았다.

결과

joystick = 0
    
for data in name:
    joystick += min(ord(data) - ord("A") , ord("Z") - ord(data) + 1)

이게 내가 적어냈던 코드의 전부였다.

느낌적으로는 상하로 움직여서 스펠링을 바꿀 때 드는 최소 횟수를 구하는 방법은 저 한 줄이 맞는 것 같았다.

이제 좌우로 움직이는 횟수만 구해서 joystick 변수에 더해주면 끝인데, 그게 떠오르지가 않았다.

검색 후 알게 된 내용

우선 내가 적었던 상하 조작에서의 최소 횟수를 구하는 방법이 맞았다는 것을 알게 되었고

정말 다행히도 다른 부분이 필요 없이 내가 생각했던 것처럼 좌우 조작 최소 횟수만 구해주면 끝이었다.

 

그리고 좌우 이동하는 횟수를 구하는데 가정되는 상황이 3개밖에 안 된다는 것에 놀랐고, 그 3개의 상황이 움직일 수 있는 모든 경우의 수라는 게 놀라웠다.

어떻게 3가지 상황으로 단정지을 수 있고, 그게 정답이 되는 걸까.

우선, 이런 경우의 수를 계산할 수 있는 분들에게 박수를 치고 싶다.

나도 제발 이런 경우의 수를 계산할 수 있는 사람이 되고 싶다.

검색 후 알게 된 풀이

def solution(name):
    joystick = 0
    default_step = len(name) - 1

    # 상하 움직임 최소 횟수 구하기
    for i, data in enumerate(name):
        joystick += min(ord(data) - ord("A"), ord("Z") - ord(data) + 1)

        # 좌우 움직임 최소 횟수 구하기
        next = i + 1
        while next < len(name) and name[next] == "A":
            next += 1

        default_step = min(default_step,
                           2 * i + len(name) - next,
                           2 * (len(name) - next) + i)
    joystick += default_step
    
    return joystick

상하 부분은 제외하고 좌우 이동 최소 횟수 구하기만 설명하려고 한다.

 

1. 좌우 이동을 하는 경우는 총 3가지로 볼 수 있다고 한다.

a. A의 유무와 상관 없이 쭉 오른쪽으로 이동하는 경우

b. 오른쪽으로 이동하다가 A를 만나게 되면 왼쪽으로 이동하는 경우

c. 바로 왼쪽으로 이동하다가 A를 만나게 되면 오른쪽으로 이동하는 경우

 

2. default_step 변수에 a의 상황에서 발생할 최소 횟수를 담아 초기화해준다.

 

3. i로 name의 요소 중 어디까지 탐색하고 있는지를 확인해준다.

이때 i의 다음 요소가 A인지 확인하기 위해서 next 변수를 초기화해준다.

 

4. next 변수에는 연속된 A 중 마지막 A가 놓여있는 인덱스가 저장된다.

 

5. b의 상황에서 발생할 최소 이동 횟수를 구하는 방법은 아래와 같다. 흐름대로 표현하겠다.

name이 JJANN이라고 해보자.

(1) A를 만나기 전 JJ를 탐색한다. 현재 i는 1이며, next는 2이다.

(2) next가 가리키는 것이 A이므로 왼쪽으로 이동하려고 한다. 그럼 다시 JJ를 탐색하게 된다. (온 길을 다시 가는 것)

(3) 왼쪽으로 이동하여 NN을 탐색한다. len(name)인 5와 next가 저장하고 있는 A 이후의 인덱스인 3 , 이 둘을 마이너스한다. 

(4) 오른쪽으로 탐색할 때 이동한 횟수 i + 다시 왼쪽으로 이동하면서 JJ를 탐색 i + (len(name) - next) => b

(5) 4를 다시 정리하자면 1 + 1 + (5 - 3) == 4 즉, 4가 b상황에서 기록되는 최소 횟수

 

6. c의 상황에서 발생할 최소 이동 횟수를 구하는 방법은 아래와 같다. 역시 흐름대로 표현하겠다.

(1) 바로 왼쪽으로 이동하여 next가 A를 가리키기 전까지 이동한다.

(2) next가 A를 가리킨다면 다시 오른쪽으로 계속해서 이동한다.

(3) 5에서와 비슷하다. 5의 반대 상황이라고 생각하면 된다. 따라서, 뒤를 탐색하는 횟수인 len(name) - next를 두 번 더해주면 된다.

(4) (len(name) - next) + (len(name) - next) 그리고 여기에 맨 앞에서부터 A가 나올 때까지 오른쪽으로 읽는 수인 i를 더해주면 끝이다.

(5) 정리하자면, 2 * (len(name) - next) + i가 c상황에서 기록되는 최소 횟수이다.

 

7. 이 3가지 상황에서 기록되는 좌우 이동 횟수 중 최소 횟수를 default_step에 담는다.

 

8. 상하 이동 횟수인 joystick 변수에 default_step을 더해준다.

 

9. joystick에 모든 최소 이동 횟수가 담겨있으니 이를 반환하면 된다.

 

느낀 점

내가 이 방법을 발견하지 못했다는 건 두말할 것 없이 마음이 아플 뿐이다.

내가 더 생각해봤다면 떠올려낼 수 있었을까?

항상 빠지게 되는 딜레마이다.

 

검색을 해야 되나?

더 생각해봐야 되나?

 

주어진 시간이 적지 않은데

모르는 문제가 많으니 조급한 마음이 들어서

검색을 하게 되는 것 같다.