SWEA - 이진 탐색 [Python]

 문제

 

- 이진 탐색으로 페이지를 검색할 때, A와 B 중 누가 더 빨리 찾는 지를 찾는다.

 

 

 

 문제 상황

 

- 찾아야할 페이지, 책의 전체 쪽 수가 주어진다. 비긴 경우는 0을 출력한다.

 

 

 

 해결 전략

 

- binary search를 사용하며 search 횟수를 기록하여 비교한다. binary search 함수를 따로 만들어 검색하게 하면 될 것 같다. 재귀로 만들 수 있다.

 

 

 

 코드

 

def binary_search(target, counts, start, end):
    c = int((start + end)/2)
    # target과 만났을 때, count 출력
    if c == target:
        return counts
    # 검색을 한번 추가하므로 counts를 1 증가시킨다.
    elif c > target :
        return binary_search(target, counts+1, start, c)
    else :
        return binary_search(target, counts+1, c, end)
 
 
T = int(input())
for idx in range(T):
    # P = 책의 쪽수, A = A가 찾아야할 페이지, B = B가 찾아야할 페이지
    P, A, B = map(int, input().split())
    pa = binary_search(A, 1, 1, P)
    pb = binary_search(B, 1, 1, P)
    if pa == pb :
        print(f"#{idx + 1} 0")
    elif pa > pb :
        print(f"#{idx + 1} B")
    else:
        print(f"#{idx + 1} A")
 
 

 

 

 해설

 

- 인덱스를 이용해 이진탐색을 구현하였다. 관찰하는 구간의 인덱스를 갱신해주며 recursive하게 처리하였다. 결과값을 비교해야하므로 recursive 요소를 return해준다.

 

 

 

 새로 학습한 것 & 실수 

 

- 문제를 잘 읽어야한다. 원래의 이진탐색이면 갱신할 때 mid값을 포함 안시켜 mid+1, mid-1 해주어야하지만 이 문제에서는 mid를 포함시켜 재정의한다.

 

 

 

 

출처 - https://swexpertacademy.com/main/