[2023-02-17 🫀 TIL ]

오늘은 백준 10815문제를 풀어보았습니다.

처음에는 이진 탐색트리를 사용하는지 몰랐지만 이진탐색을 사용하여 풀면 된다는 것을 알게 되었고
이를 코드에 적용하여 문제를 해결하였습니다.

import sys

input = sys.stdin.readline

N = int(input())
N_nums = list(map(int, input().split()))
M = int(input())
M_nums = list(map(int, input().split()))

N_nums.sort()

for m in M_nums:
    left, right = 0, N - 1
    check = False

    while left <= right:
        # print(left, right, m)
        mid = (left + right) // 2
        if N_nums[mid] > m:  # 중간 값보다 m이 작을 때 (왼쪽으로 이동)
            right = mid - 1
        elif N_nums[mid] < m:  # 중간 값보다 m이 클 때 (오른쪽)
            left = mid + 1
        else:  # 같은 값을 발견했을 떄
            check = True
            break
    print(1 if check else 0, end=' ')
 

오늘 문제로 이진탐색의 사례(?)를 알게되었습니다.