[python] 백준 1920 :: 수 찾기 (이분 탐색)

[수 찾기]

# 문제
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

# 입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

# 출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

풀이

n = input()
n_list = set(map(int, input().split()))
m = input()
m_list = list(map(int, input().split()))


for target in (m_list):
    print(1 if target in n_list else 0)

• n_list의 중복을 제거하지 않으면 시간 초과가 발생해서, set으로 변환해서 중복을 제거해야 한다!!

이분 탐색 풀이

이분 탐색

# 입력 받기
n = int(input())
n_list = list(map(int, input().split()))
m = int(input())
m_list = list(map(int, input().split()))

# 이분 탐색 함수 정의
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return 0

# 정렬 후 이분 탐색을 이용하여 m_list의 요소가 n_list에 존재하는지 확인
n_list.sort()
for target in m_list:
    print(binary_search(n_list, target))

속도 비교

• 이분 탐색을 사용하지 않은 코드가 더 빠르다..😅