[Algo] Programmers level2 조이스틱(Greedy)

Sol

참고 참고Link

def solution(name):
    
    # 조이 스틱 조작 횟수
    answer = 0
    
    # 기본 최소 좌우 이동 횟수 : 전체 길이 - 1
    min_move = len(name) - 1
    
    for i, c in enumerate(name):
        ## 상하 조작
        # 해당 알파벳 변경
        answer += min(ord(c) - ord('A'), ord('Z') - ord(c) + 1)
        
        ## 좌우 조작
        # 해당 알파벳 다음부터 연속된 A 문자열 찾기(좌우 조작)
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
        
        # 기존, 연속된 A의 왼쪽부터, 연속된 A의 오른쪽부터 방식 비교 및 갱신
        min_move = min([min_move, 2 * i + len(name) - next, i + 2 * (len(name)- next)])
        
    # 좌우이동 횟수 추가
    answer += min_move
    return answer
        
        

• 상하 이동 : ord() 함수로 해당 조이스틱을 위로 움직일지, 아래로 움직일지 값 비교
• 좌우 이동 : 기존, 연속된 A 기준 왼쪽부터 시작, 연속된 A 기준 오른쪽부터 시작 값 비교
• 연속된 A 찾기
  - while문: idx 기준으로 오른쪽에 연속된 A문자열 찾기
  • ex) "BBBAAAB"일때, idx가 2이면 next는 6이 됨
    • A문자열 길이 = (6 - 2) -1)
      • idx : 0 기준 현재 idx까지의 거리
      • (n-1) - next + 1 : 0부터 왼쪽으로 A가 아닌 알파벳까지의 거리
  • A 문자가 아니면 while문 종료, next : 연속된 A문자열 다음의 idx
  • 연속된 A 기준 왼쪽 : 2 * i + len(name) - next
    • 2 * i : 지금 온 만큼 다시 왼쪽으로 돌아가기 때문에 2 곱해줌
      • len(name) - next : 전체 길이에서 next idx만큼 뺀 길이가 연속된 A문자열의 오른쪽 부분
  • 연속된 A 기준 오른쪽 : 2 * (len(name) - next) + i

def solution(name):
    answer = 0
    n = len(name)

    def alphabet_to_num(char):
        num_char = [i for i in range(14)] + [j for j in range(12, 0, -1)]
        return num_char[ord(char) - ord('A')]

    for ch in name:
        answer += alphabet_to_num(ch)

    move = n - 1
    for idx in range(n):
        next_idx = idx + 1
        while (next_idx < n) and (name[next_idx] == 'A'):
            next_idx += 1
        distance = min(idx, n - next_idx)
        move = min(move, idx + n - next_idx + distance)

    answer += move
    return answer