[Python : 프로그래머스] 조이스틱

문제

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

풀이

LEVEL 2인거 보고 덤볐다가 3시간 넘게 피본 문제

def solution(name):
    name = list(name)
    total = 0
    i = 0
    while True :
        # 상하 조작
        total += min(ord(name[i])-65, 91-ord(name[i]))
        name[i] = 'A'
        
        if name.count('A') == len(name) : return total
        
        # 좌우 조작
        right, left = 1, 1
        for m in range(1, len(name)):
            if name[i+m] == 'A' : right += 1
            else : break
        for m in range(1, len(name)):
            if name[i-m] == 'A' : left += 1
            else : break
        
        if left < right :
            i -= left
            total += left
        else :
            i += right
            total += right

상하 조작의 경우 ASCII 값을 이용해서 구하면 쉽게 구할 수 있다.
문제는 좌우 조작에서 벌어지는데, 그리디 알고리즘을 사용해야 쉽게 통과할 수 있다.

그리디 알고리즘을 고려하지 않았을 때 등장하는 경우의 수

1. 좌에서 우로 스트레이트
2. 우에서 좌로 스트레이트
3. 좌로 향하다가 우로
4. 우로 향하다가 좌로

만일 그리디 알고리즘을 고려하지 않고 모든 경우의 수를 따지려 하면 코드가 굉장히 복잡해진다…
최초에 그리디 알고리즘 없이 접근했다가 도저히 LEVEL 2가 아닌 것 같아서,
질문 게시판을 뒤져보니 그리디 알고리즘 문제인걸 고려하라 한다.
그래서 현재 인덱스에서 ‘A’가 아닌 문자가 가장 가까이 있는 곳으로
계속 이동시키는 방식으로 구현하니 결국 통과할 수 있었다.

그리디 알고리즘은 항상 최적의 답은 내뱉지 않지만,
최악의 답은 회피할 수 있어서 사용되는 알고리즘이다!

그리디 알고리즘의 특성 때문인지, 문제가 잘못 되었다는 댓글도 굉장히 많았다.
솔직히 나도 그리디 알고리즘을 고려해보라는 힌트를 보지 못했다면
아마 문제를 포기하지 않았을까 싶다…