[BOJ] 백준 1920 수 찾기 / 이분탐색

이미지를 클릭하면 문제 사이트로 이동합니다.

 

💭 문제 이해

두 개의 정수 리스트 a, b가 주어지고,

b의 모든 원소를 비교하며 a에 존재하는 지 여부를 1과 0으로 출력하는 문제이다.

 

문제 자체는 간단하지만 완전탐색을 수행하면 10⁵ * 10⁵ = 10¹⁰ 으로 시간 초과가 발생하게 된다.

 

이 문제는 두 가지의 해결 방법이 있다.

 

1. 이분 탐색을 통해 리스트 b에서 원소를 탐색하는 시간을 log(n)으로 줄인다.

2. set()의 in 연산자는 O(1)의 시간이 걸린다는 특징을 이용하여 리스트 b를 set으로 입력받은 후, in 연산자로 탐색한다.

https://twpower.github.io/120-python-in-operator-time-complexity

 

 

 

구현 언어: Python

 

1. Binary Search

import sys

r = sys.stdin.readline


def binary_search(num, n_arr):
    left = 0
    right = len(n_arr)-1

    while left <= right:
        mid = (left + right) // 2
        if n_arr[mid] < num:
            left = mid + 1
        elif num < n_arr[mid]:
            right = mid - 1
        else:
            return 1
    return 0


n = int(r())
n_arr = list(map(int, r().split()))
n_arr.sort()
m = int(r())
m_arr = list(map(int, r().split()))

for num in m_arr:
    print(binary_search(num, n_arr))

 

2. set 자료구조 활용(시간이 절반 이상 줄어듬!!👍)

import sys

r = sys.stdin.readline

n = int(r())
n_set = set(map(int, r().split()))
m = int(r())
m_arr = list(map(int, r().split()))

for num in m_arr:
    print(1 if num in n_set else 0)