백준 10815번, bisect(), set을 이용한 원소 유무 검사

문제

10815번: 숫자 카드

 

나의 풀이

import sys
n=int(input())
sangeunCard=sorted(list(map(int,sys.stdin.readline().split())))
m=int(input())
numberCard=list(map(int,sys.stdin.readline().split()))

def binarySearch(cardList,target):
    lower=0
    upper=len(cardList)-1
    while lower<=upper:
        mid=(lower+upper)//2
        if cardList[mid]==target:
            return 1
        elif cardList[mid]>target:
            upper=mid-1
        else:
            lower=mid+1

    return 0

for i in numberCard:
    print(binarySearch(sangeunCard,i),end=' ')
# bisect함수를 이용해 binarySearch를 쉽게 구현할 수 있다.

이 풀이에서는 bisect 함수를 이용하지 않고 직접 구현하였는데 bisect 함수를 이용하면 binay search를 좀 더 쉽게 구현 할 수 있다.

bisect()함수는 bisect 라이브러리 안에 있는 함수이며

bisect_left(a,x) 는 a라는 리터러블한 객체에서 왼쪽부터 x를 찾아 그 값의 인덱스를 반환한다.

bisect_right(a,x) 또한 오른쪽 부터 탐색하는 것 말고는 bisect_left와 비슷하다.

bisect(a,x)는 bisect_right와 같다.

 

다른 사람의 풀이

n = int(input())
card = set(map(int,input().split()))
m = int(input())
for x in map(int,input().split()):
    print(1 if x in card else 0, end=' ')
#set을 활용하면 무조건 O(1) 즉 상수 시간으로 특정 원소의 유무검사를 해준다.

set을 활용하면 무조건 상수시간으로 특정 원소의 유무검사를 해준다.

 

배운 내용

binary search의 활용

bisect 함수의 활용

set을 이용하여 특정 원소 유무검사 하는 방법