[프로그래머스]조이스틱 - 그리디

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

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

 

def solution(name):
    min_move = len(name) - 1
    answer = 0
    for index, char in enumerate(name):
        # 위, 아래로 움직이는 값 구하는 부분, 유니코드를 활용해 반복문이 필요 없다.
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
    
        # 왼, 오른으로 움직일 때의 최솟값 구하기
        # 여기서 2가지의 경우가 있다. 
        # 1. 그냥 왼 -> 오 끝까지 감
        # 2. A를 만날경우 뒤로 돌아가기
        # -> 이 두가지의 경우중 최솟값을 선택해서 answer에 더해준다.
        next = index + 1
        # 2번의 경우를 구하는 while문
        # 현재 index에서 A가 연속되는 구간이 어디까지인지 파악을 한다. 
        # 이렇게 구해진 next는 연속된 A 구간의 마지막 A의 인덱스를 가리킨다.
        while next < len(name) and name[next] == 'A':
            next += 1
            
        # 적은 값 비교해서 선정, index -> 첫 A 만날 때까지 간 값 + 다시 처음으로 돌아간 값 + 나머지 부분 
        min_move = min(min_move, index + index + len(name) - next)
        
    answer += min_move
    return answer

 

문제 해결 Point

• 위아래로 움직이는 경우의 수는 유니코드의 차이 값을 이용한다.
• 좌우로 움직이는 경우의 수는 두 가지중 적은 값을 선택한다.
  1. 왼 -> 오른쪽으로 끝까지 가는 경우의 수
  2. A가 나올때까지 오른쪽으로 이동하다가 A를 만나면 왼쪽으로 이동하면서 다시 A가 나올때 까지의 경우의 수

 

BBBBAAAAB 예시

1. 1번 방법으로 구할 경우 문자열의 길이 - 1 = 8번의 좌우 이동이 이루어짐
2. 2번 방법으로 구할 경우 A를 만나기까지 3번 + 다시 처음으로 돌아가는데 3번 + 마지막 A를 만나기까지 1번 = 7번

즉, 위의 예시에서는 돌아가는 것이 더 최적이라고 할 수 있다. 해당 경우를 잘 고려하면 문제를 해결할 수 있다.

 

그럼 위의 코드를 순서대로 풀어 설명해보겠다.

1. name 리스트를 순회하면서 위 또는 아래로 움직이는 방법중 적은 값을 누적해서 더해준다.
2. next 변수를 활용하여 마지막에 등장하는 A의 인덱스를 구해준다.
3. 좌우로 움직인 횟수의 최솟값을 구해준다.
4. 마지막으로 좌우 값을 더해주면 정답을 구할 수 있다.

문제를 처음 접하였을 때, 돌아간다는 경우의 수를 복잡하게 생각하여 풀이하는데 어려웠던 문제이다. 또한, (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) 라는 조건은 적혀있지만 마지막 문자에서 처음 문자로 돌아갈 수는 없다는 것을 알아내기까지 오랜 시간이 걸렸다. (개인적으로 조건이 명시돼야 좀 더 명확한 문제라고 생각한다)