[프로그래머스] 파이썬 _ 조이스틱

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

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

문제유형 : 그리디

 

문제풀이 :

• 생각보다 안풀려서 좀 애먹었다..

 

• 나는그냥 alpha배열을 미리 만들어서 알파벳 변환의 최소비용은 쉽게 딕셔너리로 구했다.
• 좌우이동을 결정하는것에서 어려움을 겪었는데 이 문제가 그리디로 분류되있는 이유는, 현재지점에서 다음 A가아닌문자를 만날수있는 좌우이동중 더 작은 값을 갖는쪽으로 택해야하기 때문이다.
  • 즉, 바꿔야하는 문자에 다가가는 방법이 좌우가 있고, 이 값중 작은값을 택해서  결과에 더해준다. 그럼 현재문자는 A로 바뀌게된다. 이 바뀐 문자열에 대해 다시 다음 바꿀 문자열로 이동하는 최소값을 선택해야한다.

 

• 이때 유의해야 할점중 하나는 첫번째 위치에 있는 문자는 이동비용없이 알파벳 변환 비용만 더해주면 되기때문에 미리 바꿔준다.

 

 

정답코드 : 

def solution(name):
    answer = 0    
    alpha = {"A":0, 'B':1,'C':2,'D':3,'E':4,'F':5,'G':6,'H':7,'I':8,'J':9,'K':10,'L':11,'M':12,'N':13,'O':12,'P':11,'Q':10,'R':9,'S':8,'T':7,'U':6,'V':5,'W':4,'X':3,'Y':2,'Z':1}
    
    name = list(name)
    n = len(name)
    
    for i in name:
        answer += alpha[i]
    
    name[0] = 'A' #첫번째껀 이동비용없이 바꿔버림
    
    for i in range(n):
        
        if name[i]=='A':
            continue
        
        left, right = 1,1
        
        while name[i - left] == 'A':
            left += 1
            
        while i+right <= n-1 and name[i + right] == 'A':
            right += 1
        
        #print(i, left, right)
        answer += left if left < right else right
        name[i] = 'A'
        #print(name)    
    
    return answer