4839. [파이썬 S/W 문제해결 기본] 2일차 - 이진탐색

D2

Problem

SW Expert Academy 이진탐색

SW Expert Academy

---

Solution

1. 이진 탐색을 통해 원하는 값을 찾아보기
2. 이진 탐색을 위해 중앙값을 설정하고 이보다 작으면 왼쪽을 탐색, 크면 오른쪽을 탐색한다.
3. 탐색 속도를 올려주기 위해서, 찾고자 하는 값이 양 끝 값이면 바로 끝낸다.
4. 문제에서 중앙값을 계산하는 공식이 주어지기에 활용하자.
5. 카운트하는 위치를 주의하자.

---

Code

def binary_search(n, key):	# While로 구현
    cnt = 0
    start = 1
    end = n
    if 1 == key or n == key: # key가 양 끝 값인 경우
        return 0
    elif key > end or key < start: # 답이 나올 수 없는 경우
        return 0
    else:
        while start <= end:	# 가운데부터 탐색
            c = int((start + end) / 2)
            
            if c == key:		# 찾으면 끝냄
                break
            elif c > key:		# key가 중앙값보다 작으면 왼쪽 탐색
                end = c
                cnt += 1
            else:				# key가 중앙값보다 크면 오른쪽 탐색
                start = c
                cnt += 1
        return cnt				# 탐색한 횟수 리턴


for test_case in range(1, int(input()) + 1):
    P, A, B = map(int, input().split())
    a = binary_search(P, A)
    b = binary_search(P, B)
    print('#'+str(test_case), end=" ")
    if a > b:
        print('B')
    elif b > a:
        print('A')
    elif a==b:
        print('0')

<부족한 부분은 댓글로 남겨주시면 저에게 도움이 됩니다!>