[백준] 10816 : 숫자 카드 2 (Python/파이썬)

문제 링크

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

문제

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

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 
둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 
숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 
넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 
이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 
10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 
각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다

예제

입력

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

출력

3 0 0 1 2 0 0 2

---

정답 및 풀이

import sys
input = sys.stdin.readline

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

card_dict = {}

for c in cards:
    if c in card_dict:
        card_dict[c] += 1
    else:
        card_dict[c] = 1

for t in targets:
    print(card_dict.get(t, 0), end=' ')

import sys
input = sys.stdin.readline

• sys.stdin.readline()을 사용하면 입력 속도가 매우 빠르다.

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

• 숫자 카드 개수 n 입력받고 ,cards 리스트에 실제 숫자 카드 번호들을 저장한다.

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

• 찾아야 할 카드 숫자의 개수 m
• targets 리스트에 확인할 숫자들 저장한다.

card_dict = {}

• 카드의 개수를 세기 위한 딕셔너리 초기화 를 한다.

for c in cards:
    if c in card_dict:
        card_dict[c] += 1
    else:
        card_dict[c] = 1

• cards를 순회하면서
  • 이미 딕셔너리에 존재하면 1 증가
  • 존재하지 않으면 새로 추가한다.

for t in targets:
    print(card_dict.get(t, 0), end=' ')

• targets의 각 숫자에 대해
  • card_dict에서 해당 숫자의 개수를 출력한다.
  • 없는 숫자는 get(t, 0)으로 0 반환한다.
• end=' '로 한 줄에 공백으로 구분하여 출력한다.

---

새롭게 배운 내용

• get(key, default) 함수
  • key가 존재하지 않으면 default값 반환
  • 예: card_dict.get(999, 0) → 0
• 시간 복잡도
  • 카드 저장: O(N)
  • 조회: O(M)
  • 전체: O(N + M)