탐욕법 - 조이스틱** (Lv.2)

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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

 

이번에는 문제를 이해하는데 애를 먹었다.

느낌상 문제의 완성도가 높지 않은 너낌...

 

def solution(name):
    answer = 0
    # 각 알파벳별로 아스키코드로 A와의 거리가 짧은 방향(왼쪽 or 오른쪽)을 선택하여 각 알파벳별로 기본적으로 가야하는 거리 계산
    min_name = [min(ord(i) - ord('A'), ord('Z') - ord(i) + 1) for i in name]
    idx = 0
    
    # min_name에 있는 각 알파벳별 이동 횟수에 앞뒤로 A가 있는지 확인하여 A가 거리상 더 멀리 있는 방향으로 이동
    # 왼쪽과 오른쪽 방향의 커서 기능 덕분에 이것도 고려 대상이 된다.
    while True:
        answer += min_name[idx]
        min_name[idx] = 0
        if sum(min_name) == 0:
            break
        
        left,right = 1,1
        while min_name[idx - left] == 0:
            left += 1
        while min_name[idx + right] == 0:
            right += 1
        
        answer += left if left < right else right
        idx += -left if left < right else right
        
    return answer

내가 놓쳤던 부분

1.  name의 각 알파벳은 모두 A부터 시작해서 움직인다. (아래, 위 커서)
   • name = 'JAR'라고 한다면, 초기화된 상태인 A부터 시작하여 J, A, R을 만든다.
2. 만약 name에서 A가 있다면 이부분의 변경은 필요없으므로 최대한 이분을 지나지 않는 방법이 좋다.
   • BBBBBABBA[1, 1, 1, 1, 1, 0, 1, 1, 0]인 경우 

idx	answer	min_name	left	right	비고
0	1	[0, 1, 1, 1, 1, 0, 1, 1, 0]	2	1	left > right 이므로, 더 적은 쪽으로 이동
1	1+1+1	[0, 0, 1, 1, 1, 0, 1, 1, 0]	3	1	left > right 이므로, 더 적은 쪽으로 이동
2	3+1+1	[0, 0, 0, 1, 1, 0, 1, 1, 0]	4	1	left > right 이므로, 더 적은 쪽으로 이동
3	5+1+1	[0, 0, 0, 0, 1, 0, 1, 1, 0]	5	1	left > right 이므로, 더 적은 쪽으로 이동
4	7+1+1	[0, 0, 0, 0, 0, 0, 1, 1, 0]	6	2	left > right 이므로, 더 적은 쪽으로 이동 (A가 있으므로 두 칸 건너뜀)
6	9+2+1	[0, 0, 0, 0, 0, 0, 0, 1, 0]	8	1	left > right 이므로, 더 적은 쪽으로 이동
7	12+1+1	[0, 0, 0, 0, 0, 0, 0, 0, 0]	9	2	left > right 이므로, 더 적은 쪽으로 이동
9	14+2+1	END

표에 따르면, 각 인덱스 별로 A가 더 멀리 있는 방향으로 이동하는 것이 움직이는 횟수가 적다는 것을 알 수 있다.

왜나하면 '처음에는 A로 시작하여 글자가 A인 경우에는 변경없이 이동한다'는 조건에 의해, 굳이 A를 안지나가는 방법이 최소화 할 수 있기 때문이다. (A가 초기화 상태이므로 글자가 A인 경우에는 지나가지 않아도 완성)

직감적으로는 알아차리기 힘든 포인트라 이부분을 이해하는데 가장 큰 시간을 보냈던것 같다. 

 

이렇게 이해를 마치고, 여러 올라온 코드들을 실행시켜 보았지만 성공한 코드가 하나도 없다...

아마 원래는 성공했지만 테스트 케이스 추가되고 하면서 예외상황이 발생하여 그런거 같다.

그말은 문제가 완벽하지 않다는것...

 

일단 이 문제는 이쯤에서 보류해두고 다음번에 다시 봐야겠다.