백준 10816번 "숫자카드 2"

문제

백준 10816번 숫자카드2

첫번째 풀이

처음에는 이분 탐색을 진행하다 mid값과 찾으려는 수가 같다면 mid값 전 후에 같은 숫자들이 있을 것이니 해당 반복의 리스트에서 카운팅을 하는 방법으로 코드를 작성했다.
허나 이 방식으로는 시간 초과가 떳고 다시 생각해보니 최악의 경우(첫 반복에서 mid값과 찾으려는 수가 동일한 경우) 전체 리스트를 카운팅하게 된다.

첫번째 Python 코드

import sys
input = sys.stdin.readline

def bin_search(m, nums):
  if len(nums) <= 2:
    return nums.count(m)

  mid = len(nums) // 2
  if m == nums[mid]:
    return nums.count(m)
  elif m < nums[mid]:
    return bin_search(m, nums[:mid])
  else:
    return bin_search(m, nums[mid+1:])

  

n = int(input())
n_list = sorted(list(map(int, input().split())))
m = int(input())
m_list = list(map(int, input().split()))

answer = []
for x in m_list:
  answer.append(bin_search(x, n_list))

print(' '.join(str(x) for x in answer))

두번째 풀이

위 방법으로 시간 초과가 떠 해쉬 알고리즘을 이용하여 문제를 풀었다.
(파이썬에서 해쉬 알고리즘을 구현할 때 딕셔너리를 많이 사용하는 듯 하다.)

두번째 Python 코드

import sys
input = sys.stdin.readline

n = int(input())
n_list = sorted(list(map(int, input().split())))
m = int(input())
m_list = list(map(int, input().split()))

hashtable = {}

for x in n_list:
  if x in hashtable:
    hashtable[x] +=1
  else:
    hashtable[x] = 1

print(' '.join(str(hashtable[x]) if x in hashtable else '0' for x in m_list))