[Baekjoon 10816] 숫자 카드 2 | Python

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

---

문제

 

상근이가 가지고 있는 숫자 카드 묶음에서 주어진 숫자 카드들을 몇 개씩 가지고 있는지 구하는 문제이다.

 

---

풀이

 

상근이가 가지고 있는 숫자 카드 묶음은 입력받아 리스트로 만들어 주면 된다.

이 문제의 핵심은 많은 카드 가운데 해당 숫자가 적혀있는 카드를 얼마나 빨리 찾느냐는 것이다. 일반적으로 count 함수를 사용하거나, in 함수를 사용하면 리스트에서 하나 하나 탐색하기 때문에 시간 복잡도가 $ O(n) $ 이 되고, 탐색을 모든 카드에 대해 해야하기 때문에 전체 탐색 알고리즘의 시간 복잡도가 $ O(n^2 ) $ 이 되게 된다. 따라서 탐색을 빠르게 하는 것이 중요하다.

C 와 같은 언어에서는 카드 묶음을 정렬하고 이분 탐색을 이용하여 카드 묶음에서 해당 카드를 몇 개 가지고 있는지 찾아도 빠르게 찾을 수 있지만, 파이썬을 이용해서 같은 알고리즘을 활용하게 되면 번거로운 일이다. 파이썬은 딕셔너리를 이용해서 쉽게 해시 테이블을 사용할 수 있기 때문이다.

딕셔너리를 이용해서 해당 카드 묶음을 몇 개 가지고 있는지 만들어주고, 다시 딕셔너리를 이용해서 해당 카드 묶음을 몇 개 가지고 있는지 출력해주면 된다.

딕셔너리를 이용해서 카드 묶음을 몇 개 가지고 있는지 만들어줄 때 이미 만들어져 있다면 1 을 더해주면 되고, 만들어져 있지 않다면 1 로 초기화시키면서 생성해주면 된다. 출력할 때는 딕셔너리에 있다면 딕셔너리 값을, 없다면 0 을 출력해주면 된다.

 

---

코드

 

num_cards = int(input())
card_list = list(map(int, input().split()))
num_targets = int(input())
target_list = list(map(int, input().split()))
card_count = {}
for card in card_list:
    if card in card_count:
        card_count[card] += 1
    else:
        card_count[card] = 1
for target in target_list:
    if target in card_count:
        print(card_count[target], end=' ')
    else:
        print(0, end=' ')