서론
문제는 N 배열에서 M배열의 각각의 값이 몇개 존재하는지 출력하면 되는 간단한 문제이다.
다만 N과 M의 범위가 각각 500,000으로 경우의 수가 상당히 많아지기 때문에 시간복잡도가 관건이라고 생각했다.
역시나 일반적인 풀이로는 시간 초과
1. count를 이용한 풀이
import sys
input = sys.stdin.readline
n = int(input())
n_array = list(map(int, input().split()))
n_array.sort()
m = int(input())
m_array = list(map(int, input().split()))
m_array.sort()
for i in m_array:
print(n_array.count(i), end=" ")
sort를 통해 시간을 단축시켜 보았으나 시간초과
2. 이진탐색(binary search) + dictionary 를 활용한 풀이
import sys
input = sys.stdin.readline
n = int(input())
n_list = list(map(int, input().split()))
n_list.sort()
m = int(input())
m_list = list(map(int, input().split()))
# 미리 dictionary에 n의 개수 저장
n_dict = {}
for n in n_list:
if n not in n_dict:
n_dict[n] = 0
n_dict[n] += 1
def binary_search(target, array):
start = 0
end = len(array) - 1
while start <= end:
mid = (start + end) // 2
# target이 중앙값과 일치
# dictionary에서 해당 값의 합계 출력
if target == array[mid]:
return n_dict[target]
# target이 중앙값 보다 작을 경우
# 중앙값과 중앙값 우측 index 검색 제외
elif target < array[mid]:
end = mid - 1
# target이 중앙값 보다 클 경우
# 중앙값과 중앙값 좌측 index 검색 제외
else:
start = mid + 1
return 0
# 재귀함수를 통한 이진 탐색
def binary_search_recursive(target, array, start, end):
if start > end:
return 0
mid = (start + end) // 2
if target == array[mid]:
return n_dict[target]
elif target < array[mid]:
binary_search_recursive(target, array, start, mid -1)
else:
binary_search_recursive(target, array, mid +1, end)
for i in m_list:
print(binary_search(i, n_list), end=" ")
3. dictionary만을 활용한 풀이
import sys
input = sys.stdin.readline
n = int(input())
n_list = list(map(int, input().split()))
n_list.sort()
m = int(input())
m_list = list(map(int, input().split()))
n_dict = {}
for n in n_list:
if n not in n_dict:
n_dict[n] = 0
n_dict[n] += 1
for m in m_list:
# m 값이 n_dict안에 있을 경우 key에 해당하는 value의 값 출력
if m in n_dict:
print(n_dict[i], end=' ')
else:
print(0, end=' ')