숫자 개수 세기

문제

n개의 숫자가 주어지고, q개의 질문이 주어진다. 각각의 질문은 n개의 숫자 중에서 특정 숫자가 몇개나 있는지를 묻는다. q개의 질문에 모두 답하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 주어지는 q개의 질문에 해당하는 숫자 범위는 100,000,000이하이다.  

출력

각 질문에 대하여 숫자의 개수를 한 줄에 하나씩 출력한다.  

예제 입력

10 4

1 3 4 3 2 3 1 2 5 10

1 3 9 10

예제 출력

2

3

0

1

 

# 코드 

# 입력받기
n, q = map(int, input().split())
n, q = int(n), int(q)
data_list = list(map(int, input().split()))
nQ = list(map(int, input().split()))
# 가공
# 1. 중복제거(키) : 중복횟수(값) 형태로 저장한다. ex) 1:2, 2:2, 3:3 이런 형태로..
frame = {} 
for i in range(len(data_list)):
  try : frame[data_list[i]] += 1
  except : frame[data_list[i]] = 1
  
# 2. data_list에 중복 값을 제거하여 저장한다. 
set_frame = set(data_list)
data_list = list(set_frame)
data_list.sort() 
 
# 3. 이진탐색 함수
def binary_search(data, search):
  if len(data) == 1 and search == data[0]:
    return True
  if len(data) == 1 and search != data[0]:
    return False
  if len(data) == 0:
    return False
  
  medium = len(data)//2
  if search == data[medium]:
    return True
  else:
    if search > data[medium]: # 찾고자 하는 값 search값이 data[medium]보다 큰 경우
      return binary_search(data[medium+1:], search) #중간 기준 오른쪽
    else:  # 찾고자 하는 값 search값이 data[medium]보다 작은 경우
      return binary_search(data[:medium], search) #중간 기준 왼쪽
    
 
for i in range(len(nQ)):
  getRes = binary_search(data_list, nQ[i])
  if getRes == True: # True이면 값이 존재한다는 뜻 : frame 딕셔너리에서 해당 value가져오기
    print(frame.get(nQ[i]))
  else:
    print(0) # False이면 값이 존재하지 않다는 뜻 : 0을 출력한다.