[Python] 백준 #10815- 숫자 카드

문제

---

 

10815번: 숫자 카드

코드

---

My answer(시간초과)

import sys
input=sys.stdin.readline

n = int(input())
card=list(map(int,input().split()))
m=int(input())
array=list(map(int,input().split()))

for i in array:
    if(i in card):print(1,end=" ")
    else:print(0,end=" ")

My answer

import sys

n = int(input())
card=list(map(int,input().split()))
card.sort()
m=int(input())
array=list(map(int,input().split()))

def binary_search(target,start,end):
    if(start>end):
        return 0
    mid=(start+end)//2
    if(card[mid]==target):
        return 1
    elif(card[mid]<target):
        return binary_search(target,mid+1,end)
    elif(card[mid]>target):
        return binary_search(target,start,mid-1)
    
for i in array:
    answer=binary_search(i,0,len(card)-1)
    print(answer,end=' ')

Another answer

import sys

n = int(input())
card=list(map(int,input().split()))
m=int(input())
array=list(map(int,input().split()))

_dict = {}  # 속도는 dictionary!
for i in range(len(card)):
    _dict[card[i]] = 0  # 아무 숫자로 mapping

for j in range(m):
    if array[j] not in _dict:
        print(0, end=' ')
    else:
        print(1, end=' ')

import sys

n = int(input())
card=list(map(int,input().split()))
card.sort()
m=int(input())
array=list(map(int,input().split()))

for check in array:
    low, high = 0, n-1  
    exist = False
    while low <= high:
        mid = (low + high) // 2
        if card[mid] > check: 
            high = mid - 1 
        elif card[mid] < check:  
            low = mid + 1  
        else:
            exist = True
            break
    print(1 if exist else 0, end=' ')

풀이

---

우선 이 문제의 경우에도 여러가지 풀이 방법이 있었다.

첫번째 방법은 단순하게 파이썬의 내장함수 in을 이용하는 것이었는데, 내 카드를 순회하며 in을 통해 있는지 없는지만 확인하면 됐다. in의 경우에는 시간복잡도가 리스트에서는 O(N)이고, 집합이나 딕셔너리에선 O(1)~O(N)이다. 그러나 내 카드들 모두 확인해야하기 때문에 O(N^2)이 된다. 따라서 이 문제는 in을 사용하라는 문제가 아니었다.

두번째 방법은 이분탐색을 이용하는 것이었다. 이분탐색은 모든 숫자를 순회하지않기에 O(logN)이다.

따라서 우선 card리스트를 정렬하고 일반적인 이분탐색을 실시하면된다. 나는 재귀를 이용해서 구현했고 another answer 두번째에 반복문으로 구현한 이분탐색도 적어놨다.

마지막 방법은 해쉬탐색을 이용한 딕셔너리 방법이다. 이것도 그냥 카드들을 먼저 딕셔너리에 넣고 내 카드가 딕셔너리에 있는지만 확인하면 되는데 리스트처럼 앞에서부터 찾는게 아니라 키값을 통해서 찾는 것으로 속도가 빠르다.