[백준-Python] 숫자카드 : 10815번

🥈Silver 5

 

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

 

 

✅ 1차 풀이

import sys
input=sys.stdin.readline

answer=''

n=int(input())
having_cards=set(map(int,input().rstrip().split()))

m=int(input())
num_list=list(map(int,input().rstrip().split()))


for num in num_list:
    if num in having_cards:
        answer+='1'
    else:
        answer+='0'

print(' '.join(answer))

input의 범위가 10^7으로 이분탐색을 해야하나 했지만, 일단 한번 정직하게 풀어보았다.

상근이가 가지고 있는 카드가 중복이 있을수도 있고, num_list에 숫자가 일치하는지 확인하면 되기 때문에, set을 사용해서 중복을 제거해서 단순하게 in연산자로 확인하는 작업으로, 간단하게 답을 구할 수 있었다.

 

메모리	시간
121544KB	5336ms

 

여태 백준 문제 풀면서, 본 수치 중 가장 높게 나온것 같다.....  

 

✨ join이 O(n) 시간복잡도를 가지기 때문에, printe(1, end=' ')를 사용하면 된다.

 

메모리	시간
125620	612ms

 

 

✅ 이분 탐색 풀이

import sys
input=sys.stdin.readline

def binary_search(arr,target):
    left=0
    right=len(arr)-1

    while left<=right:
        mid=(left+right)//2

        if arr[mid]==target:
            return True
        elif arr[mid]<target:
            left=mid+1
        else:
            right=mid-1
    return False

answer=''

n=int(input())
having_cards=sorted(map(int,input().rstrip().split()))

m=int(input())
num_list=list(map(int,input().rstrip().split()))


for num in num_list:
    if binary_search(having_cards,num):
        print(1, end=' ')
    else:
        print(0, end=' ')

메모리	시간
108244KB	1756ms