[Beakjoon] 10816: 숫자 카드 2 - python

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

---

풀이

문제는 어렵지 않았지만 관건은 역시 시간 초과.

최초 풀이는 list를 count 하는 것으로 구현을 했으나 count 메소드는 list 전체를 순회하기 때문에 O(NM)의 매우 비효율적인 시간 복잡도가 발생한다. 따라서 조사해본 결과 collections 패키지에 Counter 클래스를 알게 되었다.

 

Counter는 list 혹은 문자열 등에서 각 요소의 개수를 자동으로 세서 딕셔너리로 만들어주는 클래스이다.
따라서 해당 클래스를 사용하면 counter() 메소드를 사용하는 것 같이 매번 모든 list를 순회하는 비효율적인 코딩을 할 필요가 없다.

import sys
from collections import Counter

n = int(sys.stdin.readline())
holded_cards = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
problem_cards = list(map(int, sys.stdin.readline().split()))

card_count = Counter(holded_cards)

for card in problem_cards:
    sys.stdout.write(str(card_count[card]) + ' ')