조이스틱 (lv2)

문제 설명

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

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

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

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

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

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

제한 사항

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

---

 가장 처음 떠올려야 하는 아이디어는 화살표를 위 아래를 조작하는 것과 양 옆으로 조작하는 것을 구분해야 한다는 것이다. 두 경우는 서로가 완전히 독립된 행동이므로, 나중에 단순히 더하기만 해도 된다.

알파벳 조작하기

 처음에 모든 문자열이 A인 문자열을 원하는 문자열로 바꾸는 방법을 생각하면 된다. 주어지는 문자열은 최대 20자 밖에 안되므로, 단순히 각 문자열을 움직인 횟수를 모두 더해주면 된다. 아스키 코드를 이용해서 화살표를 움직인 횟수를 구했다.

커서를 최소한으로 움직이기

 이 문제의 알파이자 오메가인 부분이다. 거두절미하고, 가장 중요한 전제는 조작해야할 문자를 순회하는데는 딱 네가지의 경우가 존재한다는 것이다. 그리고, 각 네 경우는 모든 문자열에 대해서 이동하는 커서의 최소값을 보장하지 않는다는 사실을 알아야한다. 즉 결국 네가지 방법을 모두 시도해본뒤 나온 결과들의 최소값이 문제의 해답이 될 것이다. 네 가지 경우는 다음과 같다.

오른쪽으로만 커서 조작

 첫 번째 인덱스부터 오른쪽 방향으로 끝까지 돌아보는 경우이다. 하지만 이 경우 역시 두 가지로 나눠서 생각할 수 있다. 예를들어 "BAAABB"라는 문자열에서는 맨 마지막 문자 'B' 까지 전부 커서를 이동시켜야 원하는 결과를 얻을 수 있을것이다. 하지만 "BABAAA"라는 문자열에 대해서는, 네 번째 문자 'A' 로는 커서를 옮기지 말고 세 번째 문자인 'B'까지만 커서를 옮겨야 할것이다. 즉 맨 마지막 문자가 'A' 인지를 확인해야한다.

왼쪽으로만 커서 조작

 첫 번째 인덱스부터 왼쪽 방향으로 끝까지 돌아보는 경우이다. 이번에도 두 가지로 나눠 생각한다. 예를 들면 "BBAABB"라는 문자열에서는 왼쪽 방향으로 진행하여 두 번째 문자 'B'까지 커서를 이동해야 할 것이다. 하지만 "BAABBB"와 같은 경우에는 네 번째 문자 'B'까지만 커서를 이동해야 왼쪽 방향으로만 진행했을 때 이동회수가 최소가 될 것이다. 즉 두 번째 문자가 'A'인지 확인해야한다.

 

 이제 나머지 두 경우를 살펴볼 것인데, 그러기 전에 이 문제의 핵심 전제를 언급하고 가겠다. 바로 연속 되는 'A'중 가장 많이 연속되는 구간은 지나지 않아야 이동회수의 최소값을 찾을 수 있다는 것이다. 실컷 앞에서 각 경우는 최소를 보장하지 않는다고 하고, 또 A가 가장 많이 연속되는 구간은 지나지 않아야 한다면서 덮어두고 오른쪽으로만, 왼쪽으로만 커서를 조작하는 경우를 따져놓고 무슨 소리냐 할 수 있다. 하지만 문자열이 "AAAAABBAAAAAAABAAA" 와 같이 주어진 경우를 생각해보자. 입력되는 문자열은 이중 연결 리스트와 같아서, 맨 처음 A 연속 구간과 맨 마지막 A 연속 구간은 사실 하나의 구간이라는 것을 생각하면 이 문자열에서 A가 가장 많이 연속되는 구간은 그 두 구간을 이은 구간이다. 말이 좀 복잡한데, 결론은 이 문제에서 입력되는 문자열은 맨 처음과 끝이 단절된 일반적인 리스트가 아닌 서로가 이어져있는 원과 같은 형태이기 때문에, 이를 1차원 배열이라 생각하고 각 문자를 순회하며 가장 반복이 많이되는 A 구간을 찾아봤자 그 구간이 정답이 아닐 수 있다는 뜻이다. 예시로 든 문자열만 해도, 시작점이 가장 긴 A 구간에 있기 때문에 가장 먼저 왼쪽 방향으로 커서를 움직여 구간을 탈출하여 여섯 번째 문자 'B'까지 도달해야 최소한으로 커서를 움직일 수 있다.

 결국 이 문제를 마주한 우리는 두가지 선택지에 놓여있다는 점을 말하고 싶다. 첫 번째는, 가장 많이 A가 반복되는 구간만 피해서 움직인다는 전제만 들고 접근하는 방법이다. 이 방법을 고른다고 생각하면, 문자열을 원형 리스트로 생각해서 가장 A가 많이 반복되는 구간을 구하고, 시작점이 하필 그 구간에 위치한지도 고려하고... 사견이지만, 가시밭길이라고 생각한다. 두 번째는, 그냥 문자열을 1차원 배열로 두고, 오른쪽으로 쭉 가는 경우, 왼쪽으로 쭉 가는 경우를 구해줘서 앞서 말한 "하필"의 경우를 커버해주는 방법이다. 본 포스트는 많은 사람들이 그러했듯 이 두 번째 방법을 이용한 접근법을 소개한다. 계속해서 나머지 경우들을 적어보겠다.

오른쪽 -> 왼쪽

 문자열을 1차원 배열로 봤을 때 가장 A가 많이 반복되는 구간을 만나기 전까지 커서를 오른쪽으로 이동한 뒤, 다시 왼쪽으로 '그 구간'을 만나기 전까지 이동시킨다. 예를 들면 "ABAAABB"에서는 (2,5) 구간이 A의 반복회수가 가장 많은데, 시작점에서 인덱스 1까지 오른쪽으로 이동하고, 다시 왼쪽 방향으로 인덱스 5까지 이동하는 것이다.

왼쪽 -> 오른쪽

 위 방법을 반대로 하면 된다.

---

코드

import re

def solution(name):
    alphabets = sum([alphabetMoves(s) for s in name])
    length = len(name)
    
    li = [c.span() for c in re.finditer('[A]+',name)]
    # 'A'가 없음
    if not li:
        return (length-1)  + alphabets
    # 'A'만 있음
    elif li[0][0] == 0 and li[0][1] == length:
        return 0
    
    rr = (length-1) + alphabets if name[-1] != 'A' else (length-(li[-1][1]-li[-1][0]))-1 + alphabets
    ll = (length-1) + alphabets if name[1] != 'A' else (length-li[0][1]) + alphabets
    rl = int(1e9)
    lr = int(1e9)

    maxSpan = max(li, key = lambda x : x[1]-x[0])
    moveRight = maxSpan[0]-1 if maxSpan[0] >= 1 else 0
    moveLeft = length-maxSpan[1]
    rl = (2*moveRight + moveLeft) + alphabets
    lr = (2*moveLeft + moveRight) + alphabets
    return min(rr,ll,rl,lr)

def alphabetMoves(c):
    up = ord(c) - 65
    down = 90 - ord(c) + 1
    return up if up <= down else down