[백준][Python][10815][이분탐색] 숫자 카드
문제 : https://www.acmicpc.net/problem/10815
10815번: 숫자 카드
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이
www.acmicpc.net
이분탐색 문제다.
list.count() 는 O(N) 이므로, count 를 사용할 경우 O(N^2) 가 되어 시간초과가 된다.
https://wiki.python.org/moin/TimeComplexity
TimeComplexity - Python Wiki
This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. Howe
wiki.python.org
따라서, 이분탐색을 적용해야 한다.
이분탐색을 적용하면 끝난다.
import sys
def binary_search(target, data):
start = 0
end = len(data) - 1
while start <= end:
mid = (start + end) // 2
if data[mid] == target:
return mid
elif data[mid] < target:
start = mid + 1
else:
end = mid -1
return None
n = int(sys.stdin.readline())
a = sys.stdin.readline().rstrip().split()
m = int(sys.stdin.readline())
b = sys.stdin.readline().rstrip().split()
a = sorted([int(i) for i in a])
b = [int(i) for i in b]
ans = []
for i in range(len(b)):
if binary_search(b[i],a) == None:
ans.append(0)
else:
ans.append(1)
for i in ans[:len(ans)-1]:
sys.stdout.write(str(i) + ' ')
sys.stdout.write(str(ans[-1]))