[프로그래머스] 조이스틱 (python)

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

프로그래머스

 

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.

ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳 
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) 
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) 
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

 

 

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

 

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

 

입출력 예

name	return
"JEROEN"	56
"JAN"	23

 

풀이

처음에는 오른쪽으로 하나씩 이동하면서 'A' 와의 차이를 구해서 더하면 되는 줄 알았는데,

조이스틱으로 첫번재 칸에서 왼쪽으로 이동하면 가장 마지막 칸으로 이동할 수 있기 때문에

타겟 문자열의 가운데에 'A'가 있을 경우 왼쪽으로 이동하는 게 더 최소가 된다.

이런 경우를 따져보면 이동의 최소화를 시키는 규칙을 찾아내는 게 굉장히 어려웠다. 😂

 

이 문제는 'A'와의 아스키 코드 차이를 구하는 건 비교적 쉽기 때문에

최소한의 이동거리를 찾는 것이 관건이다. 이를 위해서는 타겟 문자열에 ⭐A의 연속구간의 여부⭐를 잘 따져봐야 한다.

 

A의 연속구간은

A, AA, AAA, AAAA 등 A가 1개부터 N개까지 연속되는 구간을 의미한다.

그리고 이러한 A의 연속구간은 타겟 문자열의 1개 이상 존재할 수 있다.

즉, BAAB와 같이 1개가 존재할 수도 있지만, BAABAAB와 같이 2개가 존재할 수도, BAAABAAABAAB 와 같이 3개가 존재할 수도 있다.

 

여기서 타겟문자열을 만들어줄 때, 최소한으로 이동하기 위해서는

A의 연속구간 중 가장 긴 연속구간은 지나서는 안된다.

(다시 말하면 타겟 문자열을 만들기 위해서는 이외의 연속구간은 지날 수 밖에 없다.)

그러기 위해서는 A의 연속구간을 만났을 경우 돌아서 반대편으로 이동하는 횟수를 계산해야 한다.

 

이동하는 방법은 크게 세가지로 나눌 수 있는데,

1) 오른쪽으로 끝까지 쭉 이동하는 기본적인 경우

     (왼쪽으로 이동하는 경우도 있지만 결국 횟수가 동일하므로 같은 경우로 처리)

2) 오른쪽으로 가다가, 다시 왼쪽으로 돌아가서 쭉 이동하는 경우

3) 왼쪽으로 가다가, 다시 오른쪽으로 돌아가서 쭉 이동하는 경우

 

이 3가지 경우를 비교해서 가장 작은 값을 저장해줄 것이다.

하지만 A 연속구간이 가장 긴 곳이 어디부터 시작하는지, 당장 만난 A연속구간이 가장 긴 곳인지 아닌지 알 수가 없다.

 

그래서 문자열을 첫 인덱스부터 돌면서 다음 칸이 A의 연속구간인지 찾는 알고리즘을 추가한다.

그리고 해당 구간이 가장 긴지 아닌지는 따로 계산할 필요가 없다.

결국 모든 인덱스를 돌아주면서 모든 경우의 수를 다 비교할 것이기 때문이다.

 

다시 뒤돌아갈 때 기준점이 될 곳은 두가지 이다.

시작 인덱스는 항상 0이므로 1) 뒤돌아갈 인덱스, 2) 도착할 인덱스 두가지 기준점을 잡아야 하는데, 

 

처음 이동 방향이 오른쪽일 경우에는

i = 뒤돌아갈 인덱스
next = 도착할 인덱스 (A의 연속구간을 만났을 경우, 연속구간 다음 인덱스)

 

 

처음 이동 방향이 왼쪽이라면,

i = 도착할 인덱스
next = 뒤돌아갈 인덱스 (A의 연속구간을 만났을 경우, 연속구간 다음 인덱스)

 

정리하자면 우리가 반복문을 돌면서 비교할 것은 다음 3가지이다.

1) 기본 이동 횟수

2) i번째 문자까지 갔다가 뒤로 돌아서 next까지 이동

3) next까지 갔다가 뒤로 돌아서 i번째 문자까지 이동 

예시로, name이 'BBAABAAAB'일 때,

i = 0 부터 시작해 뒤로 돌아가 도착할 인덱스 next를 찾는다.

i = 0 일 경우, 다음 칸은 A의 연속구간이 아니기 때문에 도착할 인덱스틑 바로 다음 인덱스가 되어야 한다. next = i + 1

i = 1 일 경우, 다음 칸은 A의 연속구간이다. 다음 도착할 인덱스는 해당 A의 연속구간이 끝난 다음 인덱스가 되어야 한다. 

i = 4 일 경우, 다음 칸은 A의 연속구간이다. 다음 도착할 인덱스는 해당 A의 연속구간이 끝난 다음 인덱스가 되어야 한다.

 

이렇게 i를 0부터 문자열 끝까지 돌리면서 모든 이동 경우 중, 최솟값을 찾는다.

 

알고리즘 정리

1. 각 문자를 바꿔주기 위한 변경 횟수 모두 구하기 ( 조이스틱 위, 아래)

2. 모든 문자를 바꿔주기 위한 최소 이동 횟수 구하기 (조이스틱 오른쪽, 왼쪽)

3. 1)번과 2)번을 더한다.

def solution(name):
    
    gap = []
    for i in range(len(name)):
        g = ord(name[i]) - ord('A')
        gap.append(min(g, abs(26-g)))
    
    min_step = len(name) - 1
    for i, n in enumerate(name):
        
  	# 다음 칸이 A의 연속구간일 경우, 해당 구간이 끝나는 인덱스까지 이동
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
        
        right_back = 2 * i + (len(name) - next)
        left_back = 2 * (len(name) - next) + i 
        min_step = min(min_step, right_back, left_back)
        
    answer = sum(gap) + min_step
        
    return answer

 

 

 

회고

이동 횟수의 최소를 구하는 게 생각보다 많이 어렵고, 다른 블로그 해설 글을 봐도 이해하기 힘들었다.

내가 이해하기 쉽게 정리했는지는 모르겠지만, 최대한 스스로 소화할 수 있도록 풀이를 정리하고 싶었다.

이 문제는 그리디 유형인데, 만약 다시 이 문제를 처음 봤을 때로 돌아간다면 풀 수 있을지 모르겠다....

그리디는 아이디어를 생각해내야 하는 문제인 만큼, 아이디어를 생각해내는 것이 중요한데

이 문제는 아이디어를 생각해내는 것도 어렵지만, 그 아이디어를 구현해내는 것도 어려웠던 것 같다.

 

그래서 그리디 유형이지만, 구현과 완전탐색의 성격도 띄고 있는 문제이지 않나,, 생각이 들었다.

이 문제 정리하고 나니 진이 다 빠진다...

 

또한 유형을 모른 채 문제를 읽었을 때, 그리디인지 파악하는 과정도 중요한 것 같다.

요즘 어려운 그리디 문제를 많이 접하면서 그리디 유형에 자신감이 많이 떨어졌다..

그래도 다양하게 접하면서 그리디하게 해결할 수 있는 아이디어를 생각해내는 연습을 할 필요가 있다!

 

 

알고리즘 유형

• 그리디