[PROGRAMMERS]-조이스틱 (Greedy)

📃 조이스틱

풀이

• 상, 하 조작 횟수와 좌, 우 조작 횟수를 따로 구해서 더해주면 된다.
  좌, 우 조작 횟수의 경우 1) 왼쪽에서 시작해서 오른쪽으로 한방향으로만 이동하는 경우 2) 왼쪽에서 시작해서 오른쪽으로 이동하다가 방향을 바꾸어 왼쪽으로 이동하는 경우가 있다.

• 첫번째는 문자열 길이와 조작 횟수가 같다.

• 두번째는 특정 문자까지 이동한 후(해당 문자의 인덱스) 다시 처음 글자로 되돌아가(+ 해당 문자의 인덱스) 연속된 A문자의 다음 문자까지 마지막 위치에서부터 거꾸로 이동(+ 문자열 길이 - 연속된 A문자가 끝나는 위치 + 1)하면 된다.

• distance = min(idx, n - next_idx)

  • idx > n-next_inx 일 때
    ex) BHCAAN 인 경우
    B -> N -> B -> H -> C
  • idx < n-next_inx 일 때
    ex) CPAANTQ 인 경우
    C -> P -> C -> Q -> T -> N

코드

def solution(name):
    answer = 0
    n = len(name)

    def alphabet_to_num(char):
        num_char = [i for i in range(14)] + [j for j in range(12, 0, -1)]
        return num_char[ord(char) - ord('A')]
    
    # 위 아래 조작 
    for ch in name:
        answer += alphabet_to_num(ch)

    move = n - 1
    # 커서 좌우 이동 
    for idx in range(n):
        next_idx = idx + 1

        while (next_idx < n) and (name[next_idx] == 'A'):
            next_idx += 1
        
        # idx 에서 되돌아 가는 경우 /  뒤에 있는 문자열부터 갔다오는 경우 
        distance = min(idx, n - next_idx)

        # 한 방향으로만 이동하는 경우와, 오른쪽으로 이동했다가 왼쪽으로 이동하는 경우를 비교
        move = min(move, idx  + distance+ n - next_idx)

    answer += move

    return answer