[Python] 조이스틱

1. 문제

 

 

 

2. 풀이 과정

이 문제에서 답이 될 수 있는 후보는 두 가지이다.

 

1. 첫 번째는 단순히 index 0번에서 끝까지 차례대로 가면서 알파벳을 맞춰주는 것이다.

2. 두 번째는 제일 긴 A들의 연속을 피해서 둘러가는 것이다. A가 있는 건 굳이 갈 필요가 없는 곳이다.

 

제일 긴 A들의 연속만 피하고 짧은 A연속은 무시하는 이유는 예를 들어 설명하겠다.

"KFPWAAAOFAAAAAALFJ"이라는 문자열이 입력으로 들어왔다고 할 때, 굵은 글자는 무조건 가야 하는 곳이다.

OF로 가기 위해서는 짧은 A의 연속을 지나가는 것이 더 빠른 길이다.

정리하자면, A를 피해가는 방법 중에서는 제일 긴 A들의 연속을 피해 가는 것이 제일 빠른 방법이 된다.

 

또 여기서 "KFPWAAAOFAAAAAALFJ" 형광펜 칠한 부분을 지나가야되는데 가장 빠른 방법을 생각해보자. idex = 0번부터 시작해서 배열의 끝부분인 J => F => L을 바꿔준 후, 다시 idex = 0으로 돌아가서 F까지 가는 것이 가장 빠르다.

시작점(idx= 0)을 기준으로 앞, 뒤중 짧은 곳을 두 번 반복하고 긴 곳을 한 번 가면 되는 것이다.

 

def cursor(s, e):#e전까지
    if s == e:
        return 0
    else:
        return e-s-1
        
def solution(name):
    answer = 0
    start = -1
    end = -1
    max_v = [0, start, end]
    for i in range(len(name)):
    	#A의 길이가 최대인 시작, 끝 idx를 저장
        if name[i] == 'A'and start == -1:
            start = i
        elif name[i] != 'A' and start != -1:
            end = i
            if max_v[0] < end - start + 1:
                max_v = [end-start+1, start, end]
            start = -1
        #알파벳 바꿀 때 count
        answer += min(ord(name[i])-ord('A'), ord('Z')-ord(name[i])+1)
    
    if max_v[0] > 0:
    	#>>>시작점부터 A들의 시작 전까지
        p = cursor(0, max_v[1])
        #<<<A들의 끝 idx부터 배열 끝을 지나 시작점(+1)
        r = cursor(max_v[2], len(name)+1)
        #A 무시하고 직진 vs A 피해서 짧은 거리를 반복하고 긴 거리를 한 번만 가도록
        answer += min(len(name)-1, min(p, r)+p+r)
    else: #A가 없으면 직진이 빠른 길
        answer += len(name)-1
        
    return answer