[python] 프로그래머스 탐욕법(Greedy) 조이스틱

📋 문제

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

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

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동
예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

• 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
• 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
• 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
  따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
  만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항
name은 알파벳 대문자로만 이루어져 있습니다.
name의 길이는 1 이상 20 이하입니다.
입출력 예
name return
"JEROEN" 56
"JAN" 23
출처

※ 공지 - 2019년 2월 28일 테스트케이스가 추가되었습니다.

🐍 python 풀이

알파벳이 한줄로 주어지고 가장 앞에서 가장 뒤로 이동할 수 있어서 가장 가까운 알파벳을 처리하다보면 가장 적은 경우의 수로 해결할 수 있기 때문에 그리디 문제인듯하다. (아마도..)

이 문제에서 주의해야 할 것은 두 가지이다.

• 조이스틱 위 아래 이동 계산
  A에서 목표 알파벳까지의 이동 횟수를 카운트하기 쉽게 하기 위해 아스키코드값을 이용했다. A에서 이전 알파벳을 가져오면 Z가 되며 조이스틱 이용 횟수는 +1이 된다. A에서 현재 알파벳까지의 아스키코드값 차이와 Z에서 현재 알바펫까지의 아스키코드값 차이의 +1 중에서 최소값을 가져왔다. (Z로 이동하면서 1번 이동을 했으므로)

def get_updown_count(alp):
    A_ascii = ord('A')  # 65
    Z_ascii = ord('Z')  # 90
    return min(ord(alp) - A_ascii, Z_ascii - ord(alp) + 1)

• 조이스틱 양 옆으로 이동 계산
  변환이 완료한 문자를 판단하기 위해 리스트(finish)를 만들었다. 기본 0으로 이루어진 리스트이며 처리 완료한 경우 1로 바꿨다. A의 경우 처리를 하지 않아도 되므로 미리 1로 바꿔두었다.

# 입력받은 name을 기준으로 A존재 확인 -> A일 경우 이동 완료한 것으로 처리
    finish = [0] * len(name)
    for i, alp in enumerate(name):
        if alp == 'A':
            finish[i] = 1
    
    # 가장 첫번째 문자 처리(name은 1이상이기 때문에 따로 처리하지 않아도 됨)
    if finish[0] != 1:
        click_count += get_updown_count(name[0])
        finish[0] = 1

index 0부터 시작하여 좌측우측 중에서 finish 리스트의 0이 더 가까운 값을 현재 index로 바꾸고(양 옆으로 이동 카운트) 원하는 문자로 변환을 처리했다.(위 아래 이동 카운트)

def solution(name):
    click_count = 0
    
    # 입력받은 name을 기준으로 A존재 확인 -> A일 경우 이동 완료한 것으로 처리
    finish = [0] * len(name)
    for i, alp in enumerate(name):
        if alp == 'A':
            finish[i] = 1
    
    # 가장 첫번째 문자 처리(name은 1이상이기 때문에 따로 처리하지 않아도 됨)
    if finish[0] != 1:
        click_count += get_updown_count(name[0])
        finish[0] = 1
    
    index = 0
    # 나머지 문자 처리
    while finish.count(0) != 0:
        # 왼쪽 확인
        left_index = index - 1
        while finish[left_index] == 1:
            left_index -= 1
        
        # 오른쪽 확인
        right_index = index + 1
        while True:
            if right_index >= len(name):
                right_index = 0
            if finish[right_index] == 1:
                right_index += 1
                continue
            break
        
        if abs(index - left_index) < abs(index - right_index):
            now_index = left_index
        else:
            now_index = right_index
        
        click_count += abs(index - now_index)
        click_count += get_updown_count(name[now_index])
        finish[now_index] = 1
        
        index = now_index
    return click_count

def get_updown_count(alp):
    A_ascii = ord('A')  # 65
    Z_ascii = ord('Z')  # 90
    return min(ord(alp) - A_ascii, Z_ascii - ord(alp) + 1)

일단 해결은 했는데 좀 아쉬운건 있다. 현재 인덱스를 기준으로 좌측우측 중에서 거리가 더 가까운 값을 현재 인덱스로 판단하는 과정에서

if abs(index - left_index) < abs(index - right_index):

등호를 넣었을 땐 테스트 11번이 실패했는데 혹시나하고 빼보니까 성공했다. 0과의 거리가 동일한 경우에서 오른쪽으로 가야 더 경우의 수가 적은 테스트였나보다. 문제는 풀었지만 아직까진 거리가 같을 경우는 어떻게 처리해야하는지 모르겠다.

그래도 몇달 전에 풀었을 때에는 못풀어서 넘어갔던 문제인데 풀었다는 점에서 기분이 좋다.ㅎㅎ