[Python] 백준 1920번 - 수 찾기

📖 문제

1920번: 수 찾기

 

🔎 풀이

이분 탐색을 이용하는 가장 기초적인 문제입니다. 다른 아이디어 필요 없이 이분 탐색을 짜는 코드만 알고 있으면 해결이 가능합니다. 아래 코드에서 주목해야할 점은 mid 값을 계산할 때 단순히 (left + right) // 2 로 하지 않았다는 것입니다. 사실 파이썬에서는 문제될 일이 없지만, 다른 언어에서는 left + right의 값이 자료형의 최대 저장값을 넘어갈 경우 오버플로가 발생할 수 있습니다. 때문에 이를 방지하기 위해 우회하는 코드입니다.

 

💻 코드

import sys
input = sys.stdin.readline


def binary_search(num):
    left, right = 0, N-1
    while left <= right:
    	    # 오버플로우 방지 (파이썬은 상관 X)
            mid = left + (right - left)//2
            if arr[mid] > num:
                right = mid - 1
            elif arr[mid] < num:
                left = mid + 1
            else:
            	# 숫자를 찾으면 1 반환
                return 1
    # 숫자를 찾지 못하면 0 반환
    return 0


N = int(input())
# 숫자 배열
arr = [int(x) for x in input().split()]
M = int(input())
# 찾고자 하는 숫자 배열
nums = [int(x) for x in input().split()]
# 숫자 배열 정렬
arr.sort()
for num in nums:
    print(binary_search(num))