항해 TIL
이분 탐색 풀이가 난해함
난해했던 이유 : 어떻게 하면 이분 탐색을 통해 복수의 값을 찾고, 그 개수 또한 count 가능할까?
→ 결론적으로는 불가능하지는 않지만, 권장하지는 않는 풀이
1.
위의 의문이 풀리지 않아, 우선 이분 탐색으로 값이 존재하는지 확인
2.
존재하는 값은 미리 개수를 카운트해놓아 해시 맵 메모리에 보관
이진 탐색의 핵심 전제 조건은 탐색할 배열이 정렬되어 있어야 한다는 것
이진 탐색은 중간 값을 기준으로 탐색 범위를 절반씩 줄여나가는 방식으로 작동.
⇒ 이 과정에서 찾고자 하는 값이 중간 값보다 크면 오른쪽 절반을, 작으면 왼쪽 절반을 탐색합니다.
이진 탐색의 시간 복잡도 O(log n)은 정렬된 배열에서만 보장
정렬되지 않은 배열에서 이진 탐색을 사용하면, 실제로는 선형 탐색(O(n))보다 더 비효율적
n = int(input())
cards = sorted(list(map(int, input().split())))
m = int(input())
checks = list(map(int, input().split()))
cards_dict = {}
for e in cards:
if cards_dict.get(e):
cards_dict[e] += 1
else:
cards_dict[e] = 1
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] > target:
high = mid - 1
elif arr[mid] < target:
low = mid + 1
else:
return cards_dict[target]
return 0
results = [binary_search(cards, check) for check in checks]
# print()
print(' '.join(map(str, results)))
Python
복사