백준 10816번: 숫자 카드 2 -dictionary 이용 (Python)

접근

이전 글 같은 문제의 이분탐색 알고리즘을 이용한 해결에 이어, dictionary를 이용한 방법을 공부해 보았다.

2021.04.05 - [코딩/백준 (Python)] - 백준 10816번: 숫자 카드 2 -이분탐색 (Python)

백준 10816번: 숫자 카드 2 -이분탐색 (Python)

먼저 주어진 카드들을 한번 순회하면서 dictionary에 해당 카드가 몇장있는지를 저장하고, 찾아야하는 카드들을 순회하면서 해당 카드가 있는지, 몇개 있는지를 dictionary에서 찾아서 표시하는 방법이다. 이전 글에서 사용한 이분탐색의 경우, 이분탐색 자체는 전체를 순회하는 탐색보다 더 빠르지만, 이분탐색 후 좌우로 확장하면서 개수를 세는데 시간이 더 많이 필요하게 되었다. 결국 이 dictionary 방법은 전체를 순회하는 방법이지만, 이 문제의 경우에 있어서는 이분탐색보다 훨씬 더 빠른 시간 안에 답을 표시해준다.

collections 라이브러리의 Counter를 불러와 함수에 input으로 리스트를 넣어주면, (값: 개수)의 형태를 가진 dictionary로 반환해준다. 사실상 dictionary로 푸는것과 동일하다고 볼 수 있다.

코드

직접 짠 dictionary를 이용한 코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
b = list(map(int, sys.stdin.readline().split()))

dic = dict()

for i in a:
    try:
        dic[i] += 1
    except:
        dic[i] = 1

for i in b:
    try:
        print(dic[i], end=" ")
    except:
        print(0, end=" ")

collections 라이브러리의 Counter를 불러와 푸는 코드

import sys
from collections import Counter

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
b = list(map(int, sys.stdin.readline().split()))
a.sort()

counter = Counter(a)

print(' '.join(str(counter[c]) if c in counter else '0' for c in b))

더 생각해 볼 것?

이분탐색이 전체 탐색보다 빠르긴 하지만 개수를 세는데 있어서는 전체를 탐색한 것보다도 훨씬 느림을 알 수 있었다. (어쩌면 최적화가 안되서 그럴지도 모르지만)

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!