Jin의 일상

programmers.co.kr/learn/courses/30/lessons/42860

풀이 전략

조이 스틱 문제는 두 단계의 알고리즘으로 구성된다.

1. 알파벳 올리기 2. 옆으로 이동

* 참고로 옆으로 이동하는 알고리즘으로 구현할 때,

왼쪽 방향으로만 이동하거나, 오른쪽 방향으로만 이동할 수 있는 것이 아니다.

- 이런 알고리즘으로 구현하면 11번 테스트 케이스에서 틀린다.

왼쪽으로 가다가 오른쪽으로 갈 수도 있다.

ABABAAAAAAABA를 예시로 들 수 있다.

- ABAABAB가 정답이다.

1. 알파벳 올리기

- 주어진 문자열을 아스키코드로 변환한다.

    JAN  -> [74, 65, 78]  

- 대문자 A의 아스키코드는 65이므로 각 문자열의 아스키 코드에 65씩 빼준다. 

  [74, 65, 78]  => [9, 0 , 18]

- 13보다 작으면, 해당 인덱스의 값만큼 CNT에 더해준다.

- 13보다 크다면, 해당 26에서 해당 인덱스의 값을 빼서 CNT에 더해준다.

*13이 기준이 된 이유

- A~Z를 아래와 같이 나열했을 때, 제일 가운데가 되는 숫자가 13이다.

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

- 문제 조건에서 알파벳을 A,B,C 순서만이 아니고 A,Z,Y와 같이 역순으로도 셀 수 있다고 했다.

따라서 최소 CNT가 되기 위해 13을 기준으로 한다.

2. 옆으로 이동

반복문을 돌며, 각 자리에서 좌측 또는 오른쪽으로 갔을 때 최소의 움직임 횟수를 구한다.

- 0번 인덱스는 중앙에 위치한다.

- 파란색 동그라미를 시작으로 0번 인덱스의 왼쪽 방향에 위치한다.

- 0번 인덱스 오른쪽 방향에는 빨간색 동그라미까지의 인덱스 값이 위치된다.

- 0번 인덱스의 값을 기준으로, 왼쪽 끝까지 탐색하고 오른쪽 끝까지 위치했을 때 움직임 횟수를 구한다.

- 0번 인덱스의 값을 기준으로, 오른쪽 끝까지 탐색하고 왼쪽 끝까지 위치했을 때 움직임 횟수를 구한다.

- 왼쪽과 오른쪽 중 더 짧은 움직임으로 답을 갱신한다.  (비교될 움직임 횟수의 초기 값은 전체길이 - 1) 

코드

import sys


def solution(name):
    s = name
    r = list()
    
    # 알파벳 올리기/내리기
    for c in s:
        print(ord(c))
        r.append(ord(c) - 65)
    cnt = 0
    for i in r:
        if i <= 13:
            cnt += i
        else:
            cnt += (26 - i)
            
    # 옆으로 이동
    min_movement = len(r) - 1
    for red in range(len(r)):
        blue = red + 1
        while blue < len(r) and r[blue] == 0:
            blue += 1
        center = len(r) + red - blue
        LR, RL = red, len(r) - blue
        min_movement = min(min_movement, center + min(LR, RL))
    return min_movement + cnt

if __name__ == '__main__':
    R = input()
    print(solution(R))