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

출처:: programmers.co.kr/learn/courses/30/lessons/42860

분류:: 그리디

 

1. 문제 이해 및 해결과정

1) 상하 - 알파벳 바꾸는 과정 2) 좌우 - 어떤 알파벳을 바꿀지  1번과 2번의 과정이 필요하다. -> 1번은 쉽게 해결되었지만 2번이 왜 필요한지 이해가 되지 않았다.  2번의 예시는 CAAAAACCC -> 이것을 빠르게 좌우 해결하는 방법은 첫번째 C에서 오른쪽으로 가는 것이 아니라, C에서 바꾸고, 왼쪽으로 가면 마지막문자인 C로 이동함 -> 오른쪽에서 왼쪽으로 해결

 

2. 풀이방법

  1. 

def solution(name):
    res=0 #답, 알파벳변화 + 커서 이동 
    #알파벳의 횟수
    # A ~ N, N~ZA 중에 작은 수를 이동시키기
    moveAlpha= [ min(ord(ch)-ord("A"),ord("Z")-ord(ch)+1) for ch in name]
    i=0
    while True:
        res+=moveAlpha[i]
        moveAlpha[i]=0 #결과에 반영된것 
        if sum(moveAlpha)==0: #모두 반영되어 계산할 것이 없다면
            break
        left,right=1,1
        #알파벳 바꿀 필요없는 것 중 가까운것 찾음
        while moveAlpha[i-left]==0:
            left+=1
        while moveAlpha[i+right]==0:
            right+=1
        #더 가까운 것을 결과에 반영
        if left < right:
            res+=left
            i+= -left #인덱스 왼쪽으로 이동
        else:
            res+=right
            i+=right #인덱스오른쪽으로 이동 
    
    return res

 

3. 오답원인

 

4. 알게된 점