[프로그래머스] 조이스틱 (완전 탐색)

 

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

프로그래머스

 

분석

1.  조이스틱 변환 횟수 = 알파벳 변환 횟수 + 이동 횟수이므로
   1. 알파벳마다 변환 횟수를 계산해 조이스틱 변환 횟수에 추가한다.
      1. A에서 B로가는 (위로) 숫자 카운트
      2. A에서 Z로가는 (아래로) 숫자 카운트
      3. 둘 중에 최솟값을 추가
   2. 알파벳마다 이동 횟수를 계산해 최솟값을 조이스틱 변환 횟수에 추가한다.
      1. 좌,우 이동 시 바꿔야 할 남은 문자가 A뿐이면 더 진행하지 않아도 되므로 연속하는 A의 인덱스를 찾는다. 
         1. 왼쪽에서 오른쪽으로 쭉 가기 (n-1)
         2. 해당 알파벳 까지 간 뒤, 되돌아서 해당 알파벳 뒤 연속된 A전까지 가기
         3. 해당 알파벳 뒤 연속된 A전까지 간 뒤, 되돌아서 해당 알파벳까지 가기
         4. 셋 중에 최솟값을 추가이동 횟수를 계산해 조이스틱 변환 횟수에 추가한다.

 

name = "AAAABABAAAA"

name 길이 n=11

i	name	알파벳	현재 알파벳 다음 연속된 A의 인덱스	2*i + (n-현재 알파벳 다음 연속된 A의 인덱스)	i + 2 * (n-현재 알파벳 다음 연속된 A의 인덱스)	이동 최솟값 (기본값 : n-1)
0	AAAABABAAAA	A	4	7	14	7
1	AAAABABAAAA	A	4	9	15	7
2	AAAABABAAAA	A	4	11	16	7
3	AAAABABAAAA	A	4	13	17	7
4	AAAABABAAAA	B	6	13	14	7
5	AAAABABAAAA	A	6	15	15	7
6	AAAABABAAAA	B	11	12	6	6
7	AAAABABAAAA	A	11	14	7	6
8	AAAABABAAAA	A	11	16	8	6
9	AAAABABAAAA	A	11	18	9	6
10	AAAABABAAAA	A	11	20	10	6

 

풀이

def solution(name):
    answer=0 # 조이스틱 조작 횟수
    
    n=len(name)
    
    # 최소 이동 횟수는 길이 - 1
    move = len(name) -1
    
    for i,x in enumerate(name):
        answer+=min(ord(x)-ord('A'), ord('Z')-ord(x)+1) # 알파벳 변경 최솟값

        idxA = i+1 #  x다음 연속된 A 문자열 찾기
        while idxA<n and name[idxA] == 'A':
            idxA += 1
        move = min([move, 2*i+n-idxA, i+2*(n-idxA)]) # 연속된 A의 왼쪽시작, 연속된 A의 오른쪽시작
        
    answer += move # 알파벳 변경(상하이동) 횟수에 좌우이동 횟수 추가
    return answer

ㅁ