[PG] 조이스틱

[참고]

• https://bellog.tistory.com/152
• https://jokerldg.github.io/algorithm/2021/05/24/joystick.html

solution

1. 각 알파벳마다 상하 조정 중 min값으로 최소 횟수를 담아두는 배열을 만든다.
2. 0번 idx부터 시작해서 좌우 이동 횟수를 answer에 더해준다.
3. 좌우 방향 전환 시에는 바꿔야 하는 알파벳이 나오기까지의 좌우 거리를 구한뒤, 그 중 최솟값이 되는 방향으로 전환한다.
4. 모든 알파벳이 조정된 경우(change 배열이 전부 0인경우) 결과값을 반환한다.

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

크게 두 가지 방향에서 최솟값 고려
1. 상하 중 min
2. 좌우
A가 나올 때까지 next를 센다.
3. 마지막이 A로 끝날 경우

def solution(name):
    answer = 0
    min_move = len(name) - 1
    next = 0
    
    while name[min_move] == 'A' and min_move > 0:
        min_move -= 1
    
    if (min_move < 0):
        return answer
        
    for i, char in enumerate(name):
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
        
        min_move = min(min_move, i + (i + len(name)) - next)
    answer += min_move
    return answer

---

2번째..

me

1. <- -> 그리디는 생각해냈다!
2. ⬆️⬇️ 그리디는 조건 하나 생각을 덜 했다

def solution(name):
    count=0
    dicts = {'A':1,'B':2,'C':3,'D':4,'E':5,'F':6,'G':7,'H':8,'I':9,'J':10,'K':11,'L':12,'M':13,'N':14,'O':15,'P':16,
             'Q':17,'R':18,'S':19,'T':20,'U':21,'V':22,'W':23,'X':24,'Y':25,'Z':26}
    tempA=0
    A_list = []
    for n in name:
        print(abs(dicts[n]-1),abs(27-dicts[n]))
        if n!='A':
            A_list.append(tempA)
            tempA=0
            count+=min(abs(dicts[n]-1),abs(27-dicts[n]))+1
        else :
            tempA+=1
    return count+min(A_list)-1 if len(A_list)!=1 else count-1

• A 중 가장 길이가 짧은 것을 빼면 되지 않을까? 했다..

solution

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

....🥲