2021.2.10 [백준] ZOAC 2

이진 탐색 알고리즘

 

 

Q

 

www.acmicpc.net/problem/18238

18238번: ZOAC 2

 

A

 

이진 탐색 알고리즘을 이용하여 풀었다. 원판이 왼쪽, 오른쪽 둘다 돌 수 있다는 것만 주의하면 된다.

 

코드

def binary(array, target, start, end): #이진 탐색 알고리즘
    while start <= end:
        mid = (start + end) // 2 
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None
 
array = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'] #알파벳 리스트 생성
target = list(input()) #입력 받기

result = [0] #시작 위치가 0이므로 0을 먼저 넣어주기
for k in target:

    result.append(binary(array, k, 0, len(array) - 1))

 

a = 0
for i in range(len(result) - 1):
    if abs(result[i] - result[i+1]) >= 13: #원판 왼쪽으로 돌리는게 더 빠른지, 오른쪽이 더 빠른지에 따라 결정
        a += 26 - abs(result[i] - result[i+1])
    else:
        a += abs(result[i] - result[i+1])
print(a)