[class2]백준 1920번(수 찾기) - 코딩테스트 22일차(2025.02.12)

문제유형

이분 탐색

풀이 방법 도출 과정

1. 어떤 수를 찾아내는 것이기 때문에 탐색 알고리즘을 쓰면 된다. 그중 이분 탐색을 쓰겠다.

2. left, right를 설정하고 mid는 right - left 의 절반값을 쓰면된다.

3. 이제 이분 탐색법을 사용하여 문제를 풀면 된다.

 

시간 복잡도

입력 처리: O(N)

정렬: O(N log N)

M번 이진 탐색 실행 O(M log N)

 

최종 시간 복잡도

O(N log N + M log N)

코드 및 간단설명

이분탐색을 사용하여 문제를 풀었다.

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
A.sort()

M = int(input())
B = list(map(int, input().split()))

def binary_search(target):
    left, right = 0, len(A) - 1  # A의 인덱스 범위 설정
    
    while left <= right:  # 올바른 while 조건
        mid = (left + right) // 2  # 중간값 계산
        
        if A[mid] < target:
            left = mid + 1
        elif A[mid] > target:
            right = mid - 1
        else:
            return 1  # target을 찾았음
    
    return 0  # target이 없음

for num in B:
    print(binary_search(num))