DHistory
[Baekjoon] Sort, Binary Search - 2776 암기왕 본문
문제
2776번: 암기왕
연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며,
www.acmicpc.net
풀이
import sys
def solution(note1, note2):
note1 = sorted(note1)
result = []
for target in note2:
if binary_search(note1, target, 0, len(note1) - 1) != None:
result.append(1)
else:
result.append(0)
return result
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
t = int(sys.stdin.readline().rstrip())
for _ in range(t):
n = int(sys.stdin.readline().rstrip())
note1 = list(map(int, sys.stdin.readline().rstrip().split()))
m = int(sys.stdin.readline().rstrip())
note2 = list(map(int, sys.stdin.readline().rstrip().split()))
print(*solution(note1, note2), sep='\n')
채점 결과
'Computer Science > Algorithm' 카테고리의 다른 글
| [Baekjoon] DP - 10826 피보나치 수 4 (0) | 2023.09.11 |
|---|---|
| [Baekjoon] DP - 14916 거스름돈 (0) | 2023.09.11 |
| [Baekjoon] Sort - 11652 카드 (0) | 2023.09.11 |
| [Baekjoon] Sort - 1302 베스트셀러 (0) | 2023.09.09 |
| [Baekjoon] Sort - 10825 국영수 (0) | 2023.09.09 |