1. 문제

---

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/10816

2. 아이디어

---

• mine (시간 초과❗)

  1. 이진탐색으로 찾은 숫자를 이진탐색을 한 범위내에서 count해준다.

• clone1

  1. dictionary로 각 요소마다 카운트를 해서 key-value 매칭을 한다.
  2. 해당 숫자의 count 값을 출력한다.

출처 : https://tmdrl5779.tistory.com/116

• clone2

  1. bisect_left, bisect_right 사용
  2. bisect_right - bisect_left를 하면 count 할 수 있음

출처 : https://www.youtube.com/watch?v=jjOmN2_lmdk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=27

3. 코드

---

mine

import sys
input = sys.stdin.readline

def binary_search(a, x):
  start = 0
  end = len(a)-1

  while start <= end:
    mid = (start+end) // 2
    if x == a[mid]: # 발견 
      return a[start:end+1].count(x)
    elif x > a[mid]: # 찾는 값이 크면 오른쪽으로 범위를 좁혀 계속 탐색
      start = mid + 1
    else: # 찾는 값이 작으면 왼쪽으로 범위를 좁혀 계속 탐색
      end = mid - 1
  return False # 미발견

n1 = int(input())
arr1 = list(map(int, input().split()))
n2 = int(input())
arr2 = list(map(int, input().split()))
arr1.sort() # 탐색할 리스트 정렬
for i in arr2:
  result = binary_search(arr1, i)
  if result:
    print(result, end = ' ')
  else:
    print(0, end = ' ')

clone1

n = int(input())
cards = list(map(int, input().split(' ')))
cards.sort()

m = int(input())
targets = list(map(int, input().split(' ')))

dic = dict()

for i in cards:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

for i in range(m):
    if targets[i] in dic:
        print(dic[targets[i]], end=' ')
    else:
        print(0, end=' ')

출처 : https://tmdrl5779.tistory.com/116

clone2

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

def count_by_range(arr, left_value, right_value):
  right_index = bisect_right(arr, right_value)
  left_index = bisect_left(arr, left_value)
  return right_index - left_index

n1 = int(input())
arr1 = list(map(int, input().split()))
n2 = int(input())
arr2 = list(map(int, input().split()))
arr1.sort()
for i in arr2:
  result = count_by_range(arr1, i, i)
  if result == 0:
    print(0, end = ' ')
  else:
    print(result, end = ' ')

출처 : https://www.youtube.com/watch?v=jjOmN2_lmdk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=27

4. 결과 비교

---

1. mine
   시간 초과
2. clone1
   
3. clone2