10815-숫자카드

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

10815번: 숫자 카드

이분 탐색을 공부하는 중 대표 문제로 지정되어 있어서 들어가 봤더니 이전에 다른 방식으로 해결한 문제였다. 이번엔 이분 탐색을 사용하여 풀어 보았다. 

파이썬 이분 탐색 라이브러리: from bisect import bisect_left, bisect_right

이를 이용해서 리스트에 자신이 찾길 원하는 숫자가 존재하는지 확인할 수 있다..!

bisect_right(arr, i) - bisect_left(arr, i) == 정렬된 리스트 arr에서 i의 개수

 

from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
N = int(input())
have = list(map(int,input().split()))
M = int(input())
find = list(map(int,input().split()))

have.sort()

def is_possible(mid):
    return mid <= max(have)

for i in find:
    lo = bisect_left(have, i)
    hi = bisect_right(have, i)
    if hi - lo == 1:
        print(1, end=' ')
    else:
        print(0, end=' ')

 

하지만 이 문제의 경우 굳이 이분탐색을 사용할 필요는 없다. 이전에 작성했던 코드는 파이썬의 딕셔너리를 활용했는데 딕셔너리 안에서 특정 값을 찾는 연산속도는 O(1)이기 때문에 이분탐색의 O(logN)보다 더 빠르다..

import sys
input = sys.stdin.readline
N = int(input())
cards = list(map(int,input().split()))
check = {}
for i in cards:
    check[i] = 1 

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

for i in numbers:
    if i in check:
        print(1, end=' ')
    else:
        print(0, end=' ')

위는 딕셔너리 사용 코드, 아래는 이분 탐색 코드