처음에 상근이가 가지고 있는 카드 리스트에 사용할 인덱스 포인터 1개, 주어진 카드(체크할 카드)에 사용할 인덱스 포인터 1개로 총 2개의 인덱스 포인터를 사용하는 방식으로 접근하였다.
2개의 카드 리스트를 오름차순 정렬 후에 상근이 카드가 주어진 카드보다 크면 주어진 카드의 인덱스 포인터를 +1하고, 그 반대이면 상근이 카드의 인덱스 포인터를 +1하며, 2개의 카드가 같다면 2개의 인덱스 포인터를 모두 +1 하여 답을 구하는 방식으로 구현하였다. 하지만, 시간 초과가 발생하였다. 아마 while문
의 조건 혹은 for문
안의 if in문
으로 인해 O(N*M) = O(N^2)
(문제에서 N과 M의 크기가 같음)의 시간 복잡도를 가지기 때문인 것 같다. (if in문
은 모든 리스트를 전부 훑어보기 때문에 O(N)
의 시간 복잡도를 가진다고 한다.)
그래서 생각한 것은 이분 탐색
이었다. 이분 탐색
을 사용하면 O(NlogN)
의 시간 복잡도로 줄일 수 있기 때문이다. 이분 탐색
을 알고 있다면 쉽게 구현할 수 있을 것이라 생각한다. 상근이가 가지고 있는 카드를 오름차순 정렬한 후 주어진 카드에서 한 장씩 뽑아 상근이가 가지고 있는 카드 뭉치에 있는지를 반복하면 된다. (상근이가 가지고 있는 카드를 오름차순으로 정렬한 이유는 이분 탐색을 사용하기 위해서이다. 이분 탐색은 오름차순으로 정렬된 리스트에서 가능하기 때문이다.)
import sys
input = sys.stdin.readline
N = int(input())
card = list(map(int, input().split()))
M = int(input())
check = list(map(int, input().split()))
# 이분 탐색을 위한 오름차순 정렬
card.sort()
answer = [0] * M
# 이분 탐색 진행
for i in range(M):
left = 0
right = N - 1
while left <= right:
mid = (left + right) // 2
if card[mid] == check[i]:
answer[i] = 1
break
elif card[mid] < check[i]:
left = mid + 1
else:
right = mid - 1
print(*answer)