[백준/Python] 숫자카드

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

10815번: 숫자 카드

 

 

정답코드

# 숫자 카드
# 복습 횟수:2, 00:10:00, 복습필요X
import sys
si = sys.stdin.readline 

N = int(si())
own_list = list(map(int, si().split()))
own_list.sort()

M = int(si())
check_card_list = list(map(int , si().split()))


def binary_search(check_card):
    start = 0
    end = len(own_list) - 1

    while start <= end:
        mid = (start + end) // 2
        if own_list[mid] == check_card:
            return True
        
        if own_list[mid] > check_card:
            end = mid - 1
        else:
            start = mid + 1

    return False

for check_card in check_card_list:
    if binary_search(check_card):
        print(1, end= " ")
    else:
        print(0, end= " ")

 

 

풀이

1. 전형적인 이분 탐색 문제이다

2. 내가 소유한 것들을 Sort 하고 (O(N))

3. 입력으로 주어진 M개의 수를 차례로 binarySearch 하면 O(M * logN) 의 시간복잡도로 해결할 수 있다.

1 <= N, M <= 500,000이므로  시간 초과가 나지 않는다.

 

 

다른 풀이

dict 에 담아서 O(N)에 풀 수 있다.

 

코드 

# 숫자 카드
# 복습 횟수:2, 00:10:00, 복습필요X
import sys
si = sys.stdin.readline 

N = int(si())
own_list = list(map(int, si().split()))
own_list.sort()

M = int(si())
check_card_list = list(map(int , si().split()))

own_dict = dict()

for own in own_list:
    if own not in own_dict.keys():
        own_dict[own] = 1


for check_card in check_card_list:
    if check_card in own_dict.keys():
        print(1, end = " ")
    else:
        print(0, end = " ")