[Programmers][그리디] 조이스틱 python (211031)

 

코딩테스트 연습 - 조이스틱

이해도

★☆☆☆☆

 

접근방법

• 왜 이 문제가 그리디 문제일까? 생각해보았다.
• 그리디 문제인 이유는, 상하 움직이고 좌우 움직일 때 덜 움직이는 방향을 선택해야 하기 때문이다.
• 1. 상 - 하 방향의 관점 
  • A 부터 오름차순으로 알파벳을 찾는게 빠를지, Z부터 내림차순으로 찾는게 빠를지 비교한다.
    • 각 알파벳마다 상하조정 중 min 값으로 최소 횟수를 담아두는 배열을 만든다.
• 2. 좌 - 우 방향의 관점
  • 방법 1) 왼쪽에서 오른쪽으로만 이동하는 경우 + A가 나올때 까지 반대 방향으로 이동하는 경우를 비교한다.
  • 방법 2) 좌우 이동방향을 정해 바꿔야하는 알파벳이 나오기까지의 좌우거리를 구한 뒤, 그 중 최솟값이 되는 방향으로 전환
• 최종방법 1-> 1 과 2-1) 활용

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

• 최종방법 2-> 1과 2-2) 활용

프로그래머스 조이스틱 (python 파이썬) - Tech

 

풀이코드 1

def solution(name):
    name = list(name)
    answer = 0
    i = 0

    while True:
        # 왜 1을 더하는지..?
        answer += min(ord(name[i]) - ord('A'), ord('Z') - ord(name[i]) + 1)
        name[i] = 'A'

        if name.count('A') == len(name): return answer

        left, right = 1, 1
        for l in range(1, len(name)):
            if name[i - l] == 'A':
                left += 1
            else:
                break

        for r in range(1, len(name)):
            if name[i + r] == 'A':
                right += 1
            else:
                break

        if left < right:
            answer += left
            i -= left
        else:
            answer += right
            i += right

    return answer


print(solution("JEROEN"))

 

풀이코드 2

def solution(name):
    change = [min(ord(i) - ord("A"), ord("Z") - ord(i)+1) for i in name]
    idx, answer = 0, 0

    while True:
        answer += change[idx]
        change[idx] = 0

        if sum(change) == 0:
            break

        left, right = 1, 1
        while change[idx - left] == 0:
            left += 1

        while change[idx + right] == 0:
            right += 1

        answer += left if left < right else right
        idx += -left if left < right else right
        
    return answer