[프로그래머스] 조이스틱 | Greedy, Python

안녕하세요 국산엘런입니다.

 

문제 설명

요구 사항

• 조이스틱으로 알파벳 이름을 완성하시오. 

초기 상태

• 주어진 글자 수 만큼 A로만 이루어져 있음. 

규칙

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

예시

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

제한 사항

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

풀이

전처리

찾아내야할 값은 최소 이동 횟수 입니다.

먼저 이동 횟수에 영향이 없는 A를 제외시킵니다. (ASCII 코드 활용)

이때 주의할 점은 A값이 변경 여지가 없는 것이지 이동경로에는 영향을 주기 때문에, enumerate를 통해 각 알파벳의 포지션을 기억해둘 필요가 있습니다.

로직

이 문제에서 주의할 점은, 이동(알파벳 변경, 자리이동) 시 앞,뒤로 갈 수 있다는 것입니다. (맨앞 index에서 맨끝 index까지 이동거리 = 1)

먼저 알파벳 변경과 자리 이동은 분리해서 계산이 가능하기에 먼저 이동 경로만 생각해봅니다.

 

이동경로에서 중요한 점은 next index를 구하는 것입니다. 이 문제는 최소 이동경로를 구하는 문제이기에, 현재에서 가장 가까운 위치를 찾아야합니다(Greedy). 위에서 언급한 주의점 때문에, 총 4가지의 경로에서 최소값을 선택해야합니다. 

 - 앞으로 가는 2가지 (next가 현재보다 작은 index일 경우 / next가 현재보다 크지만 index 0 으로 간 뒤 끝에서 접근하는 경우)

 - 뒤로 가는 2가지 (next가 현재보다 큰 index일 경우 / next가 현재보다 작지만 끝으로 간 뒤 index 0에서 접근하는 경우)

앞으로 가는 경우엔 전처리된 리스트에서 맨앞 요소를 pop시켜 주고, 뒤로 가는 경우엔 마지막 요소를 pop시켜 줍니다. (항상 현재 요소에서 서 가장 가까운 두 값이 처음과 끝 요소임)

 

이동거리만큼 answer 를 ++ 시켜주고 알파벳 변경 횟수만큼 추가로 ++ 시켜줍니다.

 

위 작업을 전처리된 리스트가 전부 pop 될 때까지 반복합니다.

코드

def solution(name):
    answer = 0
    _name = list(filter(lambda e: e[1] > 65, enumerate([ord(c) for c in name])))

    state = 0

    while _name:
        dist_r = min(abs(_name[0][0] - state), abs(len(name) - _name[0][0] + state))
        dist_l = min(abs(_name[-1][0] - state), abs(len(name) - _name[-1][0] + state))

        if dist_r <= dist_l:
            nextState = _name.pop(0)
            answer += dist_r
        else:
            nextState = _name.pop(-1)
            answer += dist_l

        answer += min(abs(nextState[1] - 65), 1+90-nextState[1])
        state = nextState[0]

    return answer