[고득점 kit]_탐욕법_#2. 조이스틱

( 문제 설명 )

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

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

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

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

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

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

제한 사항

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

입출력 예namereturn

"JEROEN"	56
"JAN"	23

---

( 문제 해설 )

 

( 문제 해결 알고리즘 )

0. 커서의 위치는 idx = 0이 고정이 아니다 처음과 끝을 선택할 수 있다.

 

이 부분이 문제의 설명이 부족한 거 같다 개인적으로...

1. 조이스틱으로 상하로 움직일때 A-> Z -> target-alpabet, Z->A -> target-alpabet 넘어가면서 움직이는 거랑

 

1-1. A->target_alpabet으로 이동하는 거를 고려하여

 

2. 상하 움직일 때 조이스틱 획수를 카운트해준다.

 

but!!!!! 좌 -> 우로 선회하면 문제가 안 풀린다... 왜???

 

3. BBAAAB 같은 경우 끝에서 끝 인덱스에서 왼쪽 한번 이동 오른쪽 한 번 이동으로 처음 인덱스로 간 다음, 2번만 오른쪽으로 이동하면 3번이 좌, 움직임으로 해결할 수 있게 되기 때문

 

3-1. 무식하게 좌-> 우 로카운트하면 5번 다 순회해야 하니까 틀리게 되는 거죠..

 

이 부분은 그림으로 조금 자세하게 설명하겠습니다.

 

최소 좌, 우 이동 설명_그림_1

이걸 코드로 표현하면

 # i: 왼쪽 이동 ( 그림에서의 1번 이동 )
 # length - next_i: 오른 쪽이동 ( 그림에서 2번 이동 )
 # min(i, length - next_i) ( 그림에서 3번 이동 )
 
 i + length - next_i + min(i, length - next_i)

위와 같습니다.

 

---

[ 코드 ]

 

# 2. 조이스틱

def solution(name):
    answer = 0
    dic = {'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 4,
           'F': 5, 'G': 6, 'H': 7, 'I': 8, 'J': 9,
           'K': 10, 'L': 11, 'M': 12, 'N': 13, 'O': 14, 'P': 15,
           'Q': 16, 'R': 17, 'S': 18, 'T': 19, 'U': 20,
           'V': 21, 'W': 22, 'X': 23, 'Y': 24, 'Z': 25}
    res = []
    for i in range(len(name)):
        res.append('A')

    # 상, 하 이동
    for idx in range(len(res)):
        candi1 = abs(dic[name[idx]] - dic[res[idx]])  # 직접 움직이기
        candia = abs(dic[name[idx]] - dic['A'])  # 위
        candib = abs(dic[name[idx]] - dic['Z']) + 1  # 아래
        candi2 = min(candia, candib)
        candi = min(candi1, candi2)

        answer += candi

    # 좌, 우 이동
    min_move = len(name) - 1
    length = len(name)
    for i in range(length):
        next_i = i + 1
        while next_i < length and name[next_i] == 'A':
            next_i += 1
        min_move = min(min_move, i + length - next_i + min(i, length - next_i))
    answer += min_move

    return answer


# ans = 56
n = "JAN"
sol = solution(n)
print(sol)

 

---

후기

 

복습은 필수라는 걸 할 때마다 느끼네요..

어제를 기준으로 고득점 키트는 다 풀었는데..

참.. 엄청 밀렸네요..

당분간은 sql 키트 풀면서 이전에 포기했던

종 만북을 보려고 합니다.