https://www.acmicpc.net/problem/10815
시간 2초, 메모리 256MB
input :
-
N(1 ≤ N ≤ 500,000)
-
숫자 카드에 적혀있는 정수(-10,000,000 <= 정수 <= 10,000,000)
-
M(1 ≤ M ≤ 500,000)
-
숫자 카드인지 아닌지를 구해야 할 M개의 정수(-10,000,000 <= 정수 <= 10,000,000)
-
두 숫자 카드에 같은 수가 적혀있는 경우는 없다.
output : -
주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력
50만 개의 카드에 50만 개의 비교. 이중반복문으로 구하기엔 너무 크니까 이분 탐색을 생각하자.
이분 탐색을 하려면? 일단 정렬을 해야 한다.
정렬을 꼭 M에 대한 리스트에 할 필요가 없다.
M에 대해서 할 경우엔 원래의 아이템들이 어디 있는지도 기록 해야 하며,
현재의 아이템 값으로 인덱스를 다시 찾아주어야 하기 때문에 메모리, 시간적으로 손해다.
N에 대해 정렬을 하고 M에대한 리스트 값을 업데이트 하자.
import sys
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
compare = list(map(int, sys.stdin.readline().split()))
data.sort()
for idx, item in enumerate(compare):
done = False
low = 0
high = n - 1
while low <= high:
mid = (low + high) // 2
if data[mid] > item:
high = mid - 1
elif data[mid] < item:
low = mid + 1
else:
compare[idx] = 1
done = True
break
if not done:
compare[idx] = 0
for item in compare:
print(item, end=" ")그리고, 이 문제는 해당 아이템이 다른 리스트에 존재하는가? 를 묻는 문제이다.
이분 탐색이 아닌, set으로 입력을 받아 in을 이용하는 방법도 있다.
in 시간 복잡도
list, tuple
Average: O(n)
하나하나 순회하기 때문에 데이터의 크기만큼 시간 복잡도를 갖게 됩니다.
set, dictionary
Average: O(1), Worst: O(n)
내부적으로 hash를 통해서 자료들을 저장하기 때문에 시간복잡도가 O(1)가 가능하고 O(n)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생합니다.
