문제

SWEA 4839 . 이진탐색
https://swexpertacademy.com/main/talk/solvingClub/problemView.do?contestProbId=AYYWRT8qX00DFAVw&solveclubId=AYWpDVe6hEgDFAVt&problemBoxTitle=230207_%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&problemBoxCnt=3&probBoxId=AYYWQ176XvkDFAVw#none

Check point

📌 이진 탐색/ 이분 탐색/ binary search

• 자료의 중앙에 있는 원소를 고른다.
• 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
• 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
• 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.

기본 코드

💡 반복문 사용

def binary(arr, key):
    start, end = 0, len(arr) - 1
    while start <= end:
        middle = (start + end) // 2
        if arr[middle] == key:  # 검색 성공
            return True
        elif arr[middle] > key:
            end = middle - 1
        else:
            start = middle + 1
    return False  # 검색 실패

💡 재귀 사용

def binary(arr, start, end, key):
    if start > end:  # 검색 실패
        return False
    else:
        middle = (start + end) // 2
        if arr[middle] == key:  # 검색 성공
            return True
        elif arr[middle] > key:
            binary(arr, start, middle - 1, key)
        elif arr[middle] < key:
            binary(arr, middle + 1, end, key)

📌 문제 조건

• 첫 줄에 테스트 케이스 개수 T가 주어지고 테스트 케이스 별로 책의 전체 쪽 수 P 와 A, B가 찾을 쪽 번호 Pa, Pb가 차례로 주어진다.
• 각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, A, B, 0 중 하나를 출력한다.

코드

python

💡 반복문 사용

def binary(N, key): # N 전체 쪽수 
    start = 1 
    end = N
    count = 0
    while start <= end:
        middle = (start + end)//2 
        count += 1  
        if middle == key:
            return count
        elif middle > key: 
            end = middle
        else:              
            start = middle
 
T = int(input())
for tc in range(1, T+1):
    # P: 전체 쪽수 / Pa = A가 찾아야 하는 번호 / Pb = B가 찾아야 하는 번호
    P, Pa, Pb = map(int, input().split())
    #각 플레이어의 페이지
    p1_page = binary(P, Pa)
    p2_page = binary(P, Pb)
    result = '0'
    if p1_page < p2_page: # cnt가 적은 사람이 이김
        result = 'A'
    elif p1_page > p2_page:
        result = 'B'
 
    print(f'#{tc} {result}')