Greedy algorith - 코딩테스트 [탐욕법] : 조이스틱

탐욕법이란? 

- 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘입니다.
- 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있습니다.

 

그래서 최종적인 해답에 도달해야하는 알고리즘이어서 항상 최적의 값의 "근사한 값"이 목표로 구해져야한다. 

 

💡 근시안적 방법론이란?

- 단기적인 목표를 중심으로 한 전략적인 접근 방법을 의미합니다. 이 방법론은 주로 현재의 문제를 해결하는 데 초점을 맞추며, 장기적인 전망보다는 단기적인 성과를 중요시합니다.

 

그래서 오늘 풀 문제는?

- 코딩테스트 : 조이스틱

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

프로그래머스

 

어떻게 해야 가장 최적의 값을 할 수 있을까?? 

 

-> greedy 를 통해 인덱스와 이제 알파벳을 구한다

-> 알파벳 변경 횟수를 "A 방향에서 B 방향" 그리고 "A 방향에서 Z 방향" 

-> 가장 중요한 연속된 A 를 찾는 것  연속된 A를 찾는 부분 어디가 할 수 있을지 

 

def solution(name):
    
    # 알파벳 변경 횟수( 상하 이동 ) 
    spell_move = 0
    
    # 커서 이동 횟수, 이름의 길이 - 1( 좌우 이동 )
    cursor_move = len(name) - 1  
    
    
    for i, spell in enumerate(name):
    	# 알파벳 변경 횟수, 위아래 중 최소 이동 값 ( 상하 이동 )
        spell_move += min(ord(spell) - ord('A'), ord('Z') - ord(spell) + 1)
        
        # 해당 알파벳 다음부터 연속된 A 문자열 찾기
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
            
        # 아래 3가지 경우 중 최소 이동 값으로 갱신
        # 1. 이전 커서 이동 값 ( 초기값 - 이름의 길이 - 1 )
        # 2. 연속된 A의 왼쪽 시작
        # 3. 연속된 A의 오른쪽 시작
        cursor_move = min([ cursor_move, 2 * i + len(name) - next, i + 2 * (len(name) - next) ])
        
        
    # 조이스틱 조작 횟수 = 알파벳 변경 횟수( 상하 이동 ) + 커서 이동 횟수( 좌우 이동 )    
    return spell_move + cursor_move