본문 바로가기

개발/algorithm

[프로그래머스][level2] 조이스틱 - python

문제 링크

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

 

코딩테스트 연습 - 조이스틱

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다

programmers.co.kr

 

풀이 - 다른 블로그 참고 

- 이해가 잘 안돼서 다른 블로그 글을 참고해서 풀었다 .. !

+ 2022.04.21. 다시 풀이. 완전히 이해 

- 연속되는 A의 최대 거리가 핵심.

변경하는 알파벳마다 가장 긴 연속되는 A를 찾고, 왼쪽부터 시작하는 것과 오른쪽부터 시작하는 것과 그냥 일직선으로 가는 것의 이동 횟수를 구해 최솟값을 갱신한다. 

1. 처음 왼쪽에서부터 오른쪽으로 쭉 일직선으로 가는 이동 거리

2. 가장 긴 연속되는 A의 왼쪽에서 시작하는 이동 거리

3. 가장 긴 연속되는 A의 오른쪽에서 시작하는 이동거리 

알파벳마다 위 3가지 이동거리를 비교해 좌우 이동 거리의 최솟값을 갱신해주고, 마지막에 answer에 더하면 된다. 

 

def solution(name):
    answer = 0
    n = len(name)
    # 기존 왼쪽에서 오른쪽으로 이동 거리 
    min_move = n 
    
    for i in range(len(name)) :
        # 위 또는 아래로 조작하여 알파벳 완성 최솟값 
        answer += min(abs(ord(name[i])-ord('A')), abs(ord('Z')- ord(name[i]) +1))
        next = i + 1 
        
        # 연속되는 A의 최대 길이 구하기 
        while next < n and name[next] == 'A':
            next += 1 
            
        # 일직선으로 가는 것, 연속되는 A의 왼쪽에서 시작에서 이동, 연속되는 A의 오른쪽에서 시작해서 이동하는 것의 최솟값 
        min_move= min(min_move, i + i + n - next, 2*(n-next) + i )  
    
    #  최소 좌우 이동거리 더하기 
    answer += min_move
            
    return answer