[프로그래머스][python3] 조이스틱

1. 문제 설명 및 분석

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

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

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

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

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

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

“A → Z, 첫 문자열 → 끝 문자열” 경우같이 역방향으로도 조작이 가능함. 즉, 수평 이동은 첫 진행 방향의 반대로 이동했을 때 최소 이동 횟수가 나올 수 있음.

제한사항

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

입출력 예

name	return
“JEROEN”	56
“JAN”	23

2. 문제 해결

사고 과정

• 문자열 A * name의 길이를 초깃값으로, 인덱스를 하나씩 이동하며 알파벳을 name 과 동일 하게 수정
• 인덱스 이동 시 이동 횟수 + 1. 순방향 이동과 역방향 이동을 모두 고려
• 알파벳 변경 시 이동 횟수 + 변경 횟수. 알파벳 변경 횟수는 A에서 순방향 접근과 역방향 접근 이동 횟수 중 최솟값으로 사용

코드 작성

alp = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
alp_len = 26


def solution(name):
    answer = float('inf')

    # 수직 이동(알파벳 변경), 수평 이동(인덱스 변경)으로 나누어 계산
    def handler(cur_name, cur_index, ver_move, hor_move):
        nonlocal answer
        # 문자열이 일치할 때 '수직 이동 + 수평 이동 - 1' 또는 이동하지 않았을 때 0이 되도록 설정 
        if cur_name == name:
            answer = min(answer, max(ver_move + hor_move - 1, 0)) # 가장 적은 이동 횟수와 비교를 했을 때 저 적은 것을 값으로
            return
        # 수평 이동이 문자열의 길이 이상으로 가면 무의미하므로 제외
        elif hor_move >= len(name):
            return

        if cur_name[cur_index] != name[cur_index]:
            alp_index = alp.index(name[cur_index])

            # 알파벳을 동일하게 해주는 작업으로 순방향과 역방향 접근 중에 더 적은 이동 횟수를 이용
            if alp_index + 1 > alp_len / 2:
                ver_move += alp_len - alp_index
            else:
                ver_move += alp_index

            # 알파벳 변경
            list_cur_name = list(cur_name)
            list_cur_name[cur_index] = name[cur_index]
            cur_name = "".join(list_cur_name)
        # 순방향 또는 역방향으로 인덱스를 이동
        handler(cur_name, cur_index - 1, ver_move, hor_move + 1)
        handler(cur_name, cur_index + 1, ver_move, hor_move + 1)

    handler('A'*len(name), 0, 0, 0)

    return answer

제출 결과

3. 회고

• 문제의 의도는 그리디(greedy)이다. 수직 이동 횟수는 그리디 이지만, 수평 이동 횟수는 완전 탐색으로 풀었고, hor_move >= len(name) 의 브레이크 없다면 무한대로 재귀하는 경우가 발생한다.
• 수직 이동 횟수 또한 수평 이동에 달려있기 때문에 불완전하다.
• 만약 실전이었고 더 큰 범위의 인풋이 들어온다면 문제가 발생할 여지가 있다.
• 아래는 챗 GPT를 활용해 그리디 하게 문제를 해결한 코드이다.

def solution(name):
    # 알파벳 수직 이동 횟수 계산. ord 함수는 문자의 유니코드 코드 포인트로 아래와 같이 이용하면 문자 간의 차이를 계산할 수 있다.
    ver_move = sum(min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
                   for char in name)

    # 수평 이동 횟수 계산
    n = len(name)
    hor_move = n - 1  # 초깃값: 끝까지 오른쪽으로 가는 경우

    for i in range(n):
        next_i = i + 1
        # 'A'를 건너뛰기 위한 인덱스 계산. 연속되어있다면 모두 건너뛸 수 있도록 함.
        while next_i < n and name[next_i] == 'A':
            next_i += 1
        # '초깃값, 오른쪽으로 이동 후 왼쪽으로 이동, 왼쪽으로 이동 후 오른쪽으로 이동' 횟수 중 최솟값
        hor_move = min(hor_move, 2 * i + n - next_i, i + 2 * (n - next_i))

    answer = ver_move + hor_move
    return answer

• 수평 이동 횟수 계산에 대해서 설명하자면,

"XYAZAAAB" 가 인풋으로 주어졌을 경우, 'i = 3' 일 때 'next_i = 7' 일 것이다

1. 우 방향 시작: 0 → 1 → 2 → 3 → 2 → 1 → 0 → 7 (총 7회 이동)
2. 좌 방향 시작: 0 → 7 → 0 → 1 → 2 → 3 (총 5회 이동)

위와 같은 방식으로 모든 인덱스 돌며, 불필요한 이동을 제거해 이동 횟수의 최솟값을 구하는 것

• 챗 GPT 코드를 보며 그리디 접근 방식에 대해서 해석하는데 매우 힘들었다. 반대로 접근 방식을 떠올려도 코드로 작성하기 힘들 것으로 생각한다. 사고 능력을 기르도록 노력해야겠다.