[탐욕법 / 프로그래머스] 42860번 : 조이스틱

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

 

Lv2 문제다!

그렇게 어렵지 않은 문제라고 생각했는데, 좀 더 생각해야하는 부분이 있어서 난이도가 꽤 있다고 느낀 문제였다.

 

문제 이해

A로 이루어진 단어를 같은 길이의 name으로 변경하기 위한 최소 횟수를 출력하는 문제다.

경우에 따라 Z부터 시작하거나 좌우 방향을 바꿔서 진행하는 것이 작동 횟수를 더 줄일 수 있다. 

Z부터 시작하는 경우는 알파벳에 순서대로 인덱스를 할당한 후 원래 인덱스와 26 - 인덱스 값 중 최솟값을 사용하면 된다. 

하지만 좌우 방향을 바꿔야하는 경우는 진행하다가 A를 만나는 경우인데, A는 조작할 필요가 없으므로 오른쪽으로 가는 것보다 왼쪽으로 돌아서 작동하는 게 더 적은 연산일 때가 있다. 그래서 이 문제의 요점은 어떤 경우의 A를 어떻게 처리할 것인가인 것 같다. 

 

풀이 이해

주어진 name을 각 문자로 분리한 다음 A에서 가는 것과 Z에서 거슬러 오는 것 + 1(Z로 한번 이동해야하므로 + 1) 중 최솟값을 answer에 더해준다.

연속된 A의 길이를 구하기 위해서 while문을 이용한다.

min_move를 min([min_move, 2 *i + len(name) - next, i + 2 * (len(name) -next)]) 식으로 구한다.

각 문자 바꾸는 것(answer)과 이동하는 최솟값(min_value)을 더한 후 반환하면 된다 

 

위 min_move 식을 이해하기 위해 블로그에서 나온 예시를 이용했다. 

BCAAABCD

1.

연속된 A의 왼쪽으로 커서를 먼저 이동한 후, 하나씩 알파벳을 바꿔가면서 연속된 A의 오른쪽으로 이동 

주어진 순서 그대로 진행

2.

연속된 A의 오른쪽으로 커서를 먼저 이동한 후, 하나씩 알파벳을 변경하며 연속된 A의 왼쪽으로 이동

주어진 문자 뒤집은 상태로 진행 (BCDAAABC)

 

 

- 정답 풀이: 

 

참고한 블로그 

def solution(name):
    # 조이스틱 조작 횟수 
    answer = 0
    
    # 기본 최소 좌우이동 횟수는 길이 - 1
    min_move = len(name) - 1
    
    for i, char in enumerate(name):
    	# 해당 알파벳 변경 최솟값 추가
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 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

 

 

- 시도해본 풀이: 

1 / 3만 통과했던 풀이다. 

A에 대한 처리를 하지 못해서 틀린 것 같다 

 

def solution(name):
    alpha = [chr(i + 65) for i in range(26)]
    
    # 오른쪽으로 이동하는 횟수 
    answer = len(name) - 1
    
    name = list(name)
    count = 0 
    for each in name:     
        if alpha.index(each) > 25 - alpha.index(each):
            count += 1
        answer += min(alpha.index(each), 25 - alpha.index(each))
        
    if 'A' in name:
        return answer + count - 1
    else:
        return answer + count