📌 문제 요약

• 문제 이름: 10816번: 숫자 카드 2
• 알고리즘 분류: 자료 구조, 정렬, 이분 탐색, 해시를 사용한 집합과 맵
• 사용 언어: Python 3

숫자 카드 $N$개가 주어졌을 때, 정수 $M$개가 주어지면 이 수가 적혀있는 숫자 카드를 상근이가 각각 몇 개 가지고 있는지 구하는 문제입니다. 단순한 탐색 문제 같지만, $N$과 $M$의 범위가 각각 최대 500,000이므로 일반적인 선형 탐색($O(N)$)을 사용하면 시간 초과가 발생합니다.

---

💡 문제 접근 방법 (핵심 로직)

이 문제는 빠른 탐색이 필요하므로 이분 탐색(Binary Search)을 활용해야 합니다. 파이썬에서는 bisect라는 강력한 내장 라이브러리를 제공하기 때문에 직접 이분 탐색 로직을 짤 필요 없이 매우 간결하게 풀이할 수 있습니다.

1. 정렬: 이분 탐색을 사용하기 위한 필수 전제 조건으로, 상근이가 가진 카드 리스트(card)를 먼저 오름차순으로 정렬합니다. 시간 복잡도는 $O(N \log N)$입니다.
2. 개수 구하기 (Upper Bound - Lower Bound):
   • bisect_left(배열, 값): 배열에서 해당 값을 삽입할 가장 왼쪽 인덱스 (Lower Bound)
   • bisect_right(배열, 값): 배열에서 해당 값을 삽입할 가장 오른쪽 인덱스 (Upper Bound)
   • 정렬된 배열에서 특정 값의 개수 = bisect_right 결과 - bisect_left 결과가 됩니다.
   • 탐색 시간 복잡도는 하나당 $O(\log N)$이므로, 총 $M$개를 찾을 때 $O(M \log N)$이 소요됩니다.

---

💻 코드 구현

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline

N = int(input())
card = list(map(int, input().split()))
M = int(input())
card_find = list(map(int, input().split()))

# 이분 탐색을 위한 정렬
card.sort()

# 우측 경계 인덱스에서 좌측 경계 인덱스를 빼서 요소의 개수를 구함
for i in card_find:
    print(bisect_right(card, i) - bisect_left(card, i), end=' ')

🚨 트러블 슈팅 및 회고
시간 초과(Time Out) 방지: 처음에 코드 상단에 import sys를 선언해 두고 정작 sys.stdin.readline을 사용하지 않았습니다. 데이터가 최대 50만 개나 되기 때문에 기본 input()을 사용하면 입력을 받는 과정에서부터 시간 초과가 날 수 있다는 점을 상기하고, 대량 입력 시에는 반드시 sys.stdin.readline을 습관화해야겠습니다.

다른 접근법 고민 (Hash Map): 이분 탐색으로도 훌륭하게 풀리지만, 파이썬의 딕셔너리(Dictionary)나 collections.Counter 모듈을 사용하면 카드의 개수를 세는(Counting) 작업과 찾는 작업을 시간 복잡도 $O(N+M)$으로 더 빠르게 처리할 수 있습니다. 다음에는 이분 탐색 외에 해시맵을 이용한 방식으로도 접근하여 실행 시간을 비교해 보아야겠습니다.

---

💡 [추가 풀이] 파이썬다운 완벽한 최적화: 해시맵(Counter)

위 회고에서 고민했던 내용의 해답입니다. 이 문제는 분류상 '이분 탐색'에 속해 있지만, 사실 파이썬 생태계에서는 해시맵(Hash Map) 자료구조를 이용해 푸는 것이 압도적으로 빠르고 간결한 '정석'으로 통합니다.

파이썬의 내장 모듈인 collections.Counter를 사용하면, 복잡한 정렬이나 이분 탐색 과정 없이 데이터의 개수를 단숨에 세어버릴 수 있습니다.

💻 코드 구현 (Counter 활용)

import sys
from collections import Counter

input = sys.stdin.readline

# 1. 상근이가 가진 카드 입력
N = int(input())
# 카드를 정수로 변환하지 않고 문자열 리스트 그대로 둡니다.
cards = input().split() 

# 2. Counter를 이용해 각 카드에 적힌 숫자가 몇 개씩 있는지 해시맵 생성
card_count = Counter(cards)

# 3. 찾아야 할 타겟 카드 입력
M = int(input())
targets = input().split()

# 4. 해시맵에서 타겟 카드의 개수를 O(1)로 찾아서 배열에 담기
answer = []
for target in targets:
    # .get(찾을키, 기본값): 해당 키가 없으면 0을 반환합니다.
    answer.append(str(card_count.get(target, 0)))

# 5. 리스트 요소들을 공백으로 이어붙여 한 번에 출력
print(' '.join(answer))

⚖️ 성능 비교: 이분 탐색 vs Counter(해시맵)

왜 이 문제에서 해시맵이 이분 탐색보다 빠를까요? 아래의 시간 복잡도 표를 보면 직관적으로 알 수 있습니다.

비교 항목	이분 탐색 (bisect)	해시맵 (Counter)
사전 작업	card.sort() 배열 정렬: $O(N \log N)$	Counter(cards) 개수 세기: $O(N)$
탐색 속도 (1건)	반씩 쪼개며 찾기: $O(\log N)$	키(Key)로 바로 찾기: $O(1)$
총 소요 시간	$O(N \log N + M \log N)$	$O(N + M)$
강점	'범위(A~B)' 안의 데이터 개수를 구할 때	'정확히 일치'하는 값의 개수를 구할 때

결론적으로, 단순히 "특정 카드가 정확히 몇 장 있는가?"를 묻는 문제에서는 굳이 리스트를 정렬하고 이분 탐색을 하는 것보다, 데이터를 해시 테이블(사전)에 넣어두고 즉각적으로( $O(1)$ ) 꺼내보는 방식이 속도와 코드 간결성 모든 면에서 훨씬 유리합니다.