[백준/파이썬] 10816번 숫자 카드 2 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 10816번 숫자 카드 2
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

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

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

n=int(input())
a=list(map(int,input().split()))
m=int(input())
b=list(map(int,input().split()))

d=dict()
for i in a:
    try:d[i]+=1
    except:d[i]=1
r=[]
for i in b:
    try:r.append(d[i])
    except:r.append(0)
print(' '.join(map(str,r)))

설명

수의 범위가 2천만이 넘고, 입력되는 숫자도 최대 50만씩 두번에 달합니다.

이래서야 단순한 순차탐색은 불가능하고, 이분 탐색은 복잡도가 O(log n)이므로 해당 알고리즘을 사용하면 풀 수 있습니다.

하지만, 저는 여기서 좀 더 간단하게 풀겠습니다.

수의 범위는 2천만여개이지만, N이 50만이라는 점에서 충분히 딕셔너리를 응용할 여지가 남아있습니다. 50만 * 4바이트 <= 2MB 입니다. 공간복잡도가 허용범위 내이므로, 입력받은 수가 몇개인지를 딕셔너리에 저장했다가, 해당 수를 바로 조회하면 됩니다. O(1)의 시간 복잡도로 접근가능합니다. 또, 모든 수를 저장하는 것도 아니므로 일반적인 이분 탐색법에 비해 공간 자원도 근소하게 우위를 가집니다. 구현하기도 훨씬 쉽습니다.

---

• 백준 문제풀이 전체 목록 보기

---