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

📜 LV2. 조이스틱

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

😕 어떻게 풀었지?

def solution(name):
    answer = 0
    shift = len(name) - 1
    
    for i, char in enumerate(name):
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1) #알파벳 선택

        if(char == 'A'): #이동
            target = i
            while(target<len(name) and name[target] == 'A'):
                target += 1
            if (i == 0):
                left = 0
            else:
                left = i-1
            
            right = len(name) - target
            shift = min(shift, left+right+min(left, right))
            
    answer += shift
    return answer

허허,... 테스트케이스가 엄청 많았다. 시간을 너무 많이 끌었다.

1. 나는 처음에 A~J까지 바꾼다하면, 타켓 알파벳이 아스키코드로 A~Z의 중간 알파벳보다 작다면 왼쪽부터 증가, 아니면 오른쪽부터 감소. 이렇게 굉장히 복잡하게 if문, while문으로 다 계산해서 answer를 증가시켰다. 아.. 근데 아래처럼 최고로 간단한 방법이 있더라.

answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)

2. A가 등장했다? 그러면 A가 연속으로 나오는지 확인할 필요가 있었다.
   2-1. A로만 이루어진 문자열(예를 들면 'HIBAAAAAACGOOD')의 왼쪽커서와 오른쪽 커서 위치를 알아낸다.
3. shift(=이동횟수)는 맨 처음에 기본값으로 한 방향으로만 계속 이동했을 때의 값(=len(name)-1)로 지정해두었다.
   3-1. shift는 요구사항처럼 최솟값이 되어야한다. 따라서 기존의 shift값과, left+right+min(left, right)중에 최솟값을 선택해서 그 값으로 한다. 이를 계속 갱신하고 맨 마지막에 answer에 더하고 끝!

shift = min(shift, left+right+min(left, right))

'HIBAAAAAACGOOD'

난 여기서 shift값을 갱신하고자 한다. 근데 왼쪽 처음부터 오른쪽으로 갔다가 다시 유턴하는 게 더 최솟값일까, 아니면 오른쪽 끝부터 왼쪽으로 갔다가 다시 유턴하고 가는 게 더 최솟값일까? 왼쪽이다. (min(left, right)에서 left 선택.)

1. shift가 기본값이다. → 14
2. shift = left + right + left → 2 + 7 + 2 = 9 (⭕)
3. shift = left + right + right → 2 + 7 + 7 = 16

✅ 처음 알았다

1) 파이썬에서 문자의 아스키코드를 출력할 때 int('A') 이런 식으로 형변환을 하는 줄 알았는데, 그게 아니라 ord('A')로 한다. 이렇게 했을 때 type은 int.

2) 이 문제는 백준에도 수록되어있는 문제다. ➡ https://www.acmicpc.net/problem/3663