[이분탐색] 백준 #10815 숫자 카드 - Python

🗂️ 문제

링크: https://www.acmicpc.net/problem/10815

 

💡 접근법

이분탐색 시 탐색 범위를 설정해야 한다. 해당 문제에서는 카드 리스트를 정렬하고, 카드 리스트 인덱스의 최솟값(0)과 최댓값(len(card_list)-1)을 low와 high로 각각 지정한다.

 

mid의 값을 변경하며 탐색한다. 이때 카드 리스트에서 mid 인덱스에 해당하는 값보다 상근이가 가지고 있는 숫자가 작으면 mid 값을 줄여야하므로 high = mid - 1로 설정한다. 반대의 경우엔 mid 값을 키워야하므로 low = mid + 1로 설정한다.

 

만약 카드 리스트에서 mid 인덱스에 해당하는 값이 상근이가 가지고 있는 숫자와 같다면 1을 저장한다.

 

😎 내 코드

import sys

N = int(sys.stdin.readline())
card_list = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())
num_list = list(map(int, sys.stdin.readline().split()))

card_list.sort()

result = [0] * len(num_list)
for idx, num in enumerate(num_list):
    low = 0  # 인덱스의 최솟값
    high = len(card_list) - 1  # 인덱스의 최댓값

    while (low <= high):
        mid = (low+high) // 2  # 인덱스
        mid_value = card_list[mid]

        if mid_value == num:
            result[idx] = 1
            break
        elif mid_value > num:
            high = mid - 1
        elif mid_value < num:
            low = mid + 1
    
print(*result)

 

🧐 배운 점

• python의 in 함수는 선형탐색이므로 시간복잡도가 O(n)이다. 즉, 이분탐색보다 느리다.

 

✅ 정답 확인