[백준(python)] 10816 숫자 카드2

📌 난이도, 유형

난이도 : 실버4
유형 : 자료구조, 정렬, 이분탐색, 해시를 사용한 집합과 맵
시간제한 : 1초
메모리제한 : 256MB

---

📌 문제설명

---

📌 입출력 예

---

📄 코드

이분탐색사용

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

N = int(input())
array = list(map(int, input().split()))
array.sort()
M = int(input())
array2 = list(map(int, input().split()))
for i in range(M):
    target = array2[i]
    count = bisect_right(array, target) - bisect_left(array, target)
    print(count, end=" ")

딕셔너리 사용

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))
dic = {i: 0 for i in arr2}

for i in arr:
    if i in dic:
        dic[i] += 1

for num in arr2:
    print(dic[num], end=" ")

---

📝 해설

전형적인 이분탐색 문제
array를 오름차순으로 정렬 후 bisect를 사용해 목표값(target)의 위치를 찾아 오른쪽 - 왼쪽을 해주어서 몇개인지 구하였다

파이썬의 딕셔너리로도 풀 수 있다.

# 딕셔너리를 생성
dic = {i: 0 for i in arr2}

이후 array를 하나씩 돌면서 딕셔너리에 하나씩 추가해준다.

for i in arr:
    if i in dic:
        dic[i] += 1

마지막으로 딕셔너리에 저장된 값을 출력해주면 끝

1번 : 딕셔너리 사용
2번 : bisect 사용