[프로그래머스] 탐욕법 2. 조이스틱

출처: 프로그래머스

---

풀이

def solution(name):
    answer = len(name) - 1
    
    for i in range(0, len(name)):
        nameASCII = ord(name[i])
        if nameASCII > 78:
            answer += (90 - nameASCII + 1)
        else:
            answer += (13 - 78 + nameASCII)
    
    lenOfFrontA = 0
    for i in range(1, len(name)):
        if name[i] == 'A':
            lenOfFrontA += 1
        if name[i] != 'A':
            break
    
    lenOfBackA = 0
    for i in range(len(name) - 1, -1, -1):
        if name[i] == 'A':
            lenOfBackA += 1
        if name[i] != 'A':
            break
    
    
    return answer - max(lenOfFrontA, lenOfBackA)

첫번째 포문에서 알파벳을 변경하는 조작횟수를 계산하고 두 번째, 세 번째 포문에서 연속되는 a만큼의 자리 이동 조작 횟수를 빼려고 했다.

 

근데 자꾸 11번째 케이스에서 실패했다. 검색해보니 ABABAAAAABA 의 경우에서 통과해야한다고 한다.

내 코드는 탐욕법을 적용하고 있지 않아 전면적으로 수정해야 했다. 잘 떠오르지 않아 다른분의 코드를 봤다.

처음엔 로직만 참고하려고 했는데, 내가 짜니 코드가 길어지고 조건문이 더러워져서 결국 거의 다 따라했다.

로직도 문법 활용도 좋아서 깔끔한 코드였다. 언제쯤 나도 이렇게 짤 수 있을가..,,

참고한 블로그: whwl.tistory.com/93

def solution(name):
    change = [min(ord(name[i]) - ord('A'), ord('Z') - ord(name[i]) + 1) for i in range(len(name))]
    idx = 0
    answer = 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