2021.2.10 [백준] ZOAC 2
이진 탐색 알고리즘
Q
18238번: ZOAC 2
2019년 12월, 두 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 작년 ZOAC의 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해
www.acmicpc.net
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)