[백준] 숫자 카드

✏️ 문제

10815번: 숫자 카드

✏️ 풀이

찾고자 하는 값이 주어진 리스트에 있는 지 찾아보는 문제이다.

아이디어는 매우 간단하지만 만약 list의 in 연산자를 사용한다면 한 번 탐색하는 데 O(N)이 걸리므로 시간 초과가 예상된다.

따라서 O(logN)의 binary search 알고리즘을 이용하여야 한다.

✏️ 코드

- 풀이 1 : Binary Search 이용

from bisect import bisect_left, bisect_right

n = int(input())
cards = sorted(list(map(int, input().split())))
m = int(input())
find = list(map(int, input().split()))

for i in find:
    exist = bisect_right(cards, i) - bisect_left(cards, i)
    print(exist, end=" ")

카드 배열을 정렬한 후 찾는 카드에 대해 이진 탐색한다.

파이썬에서 제공하는 bisect 모듈을 사용하였다.

이에 대해 정리하였다. (seonyounggg.tistory.com/173)

 

- 풀이 2 : Set 사용

n = int(input())
cards = set(map(int, input().split()))
m = int(input())
find = list(map(int, input().split()))

for i in find:
    if i in cards:
        print(1, end=" ")
    else:
        print(0, end=" ")

Python에서의 Set은 Hash 기반이므로 삽입/삭제/탐색이 O(1) 이다.

(C++의 경우, Set은 Binary Search tree 기반이므로 삽입/삭제/탐색이 O(logn) 이다.)

따라서 카드 배열을 Set으로 만들고, Set의 in 연산을 통해 시간제한 내에 값을 구할 수 있다.

이 풀이는 정렬이 필요하지 않다.

 

채점 결과 풀이 2가 조금 더 빠르게 나왔다.