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

첫 번째 시도

# 해시 테이블 전체 코드 
import sys

hashTable = [[] for i in range(100000)]

N = sys.stdin.readline().rstrip()

for i in list(map(int, sys.stdin.readline().split())) :
    hashVal = i % 100000
    hashTable[hashVal].append(i)

M = sys.stdin.readline().rstrip()
for i in list(map(int, sys.stdin.readline().split())) :
    hashVal = i % 100000
    print(hashTable[hashVal].count(i))    

1. 해시 테이블에 상근이가 가지고 있는 N개의 카드를 저장한다.
   해시 테이블은 이차원 배열로 생성
   카드 숫자를 100,000으로 나눈 나머지를 해시 테이블의 인덱스로 사용
2. M개의 카드 중 상근이가 몇 개의 카드를 있는지 체크한다.
   해시 테이블 인덱스를 이용해 숫자가 저장된 배열을 찾는다.
   해당 배열을 순회하면서 해당 숫자가 몇 개인지 센다.

시간 초과 발생

추측이기는 하지만
해시 테이블 인덱스에 해당하는 배열을 탐색할 때, 모든 원소가 하나의 배열로 들어가 있다면 탐색 시간이 길어지는 문제 발생 

결과

두 번째 시도

# 딕셔너리 사용 
import sys 

N = sys.stdin.readline().rstrip()
dic = dict()

for i in list(map(int, sys.stdin.readline().split())) :
    if dic.get(i) :
        x = dic.get(i)
        x = x + 1
        dic[i] = x
    else :
        dic[i] = 1

M = sys.stdin.readline().rstrip()
for i in list(map(int, sys.stdin.readline().split())) :
    if dic.get(i) :
        print(dic.get(i), end=" ")
    else :
        print(0, end=" ")

1. 딕셔너리의 key 값은 숫자를 의미하고, value 값은 동일한 숫자 카드 개수로 가정
   • 만약 딕셔너리에 해당 key에 해당하는 데이터가 존재하면, value 값을 읽어와 1을 더한 후 다시 딕셔너리에 저장한다.
   • 만약 딕셔너리에 해당 key에 해당하는 데이터가 없다면, value가 1이고 숫자를 key로 갖는 딕셔너리를 저장한다.
2. 이후 검색할 숫자들을 딕셔너리에서 검색하여 개수를 센다.

결과

딕셔너리도 해시테이블을 사용하는데 왜 첫 번째 시도는 안 되는가 ??

첫 번째의 경우 해시 테이블을 사용하여 탐색을 수행하고, 또 해당 배열에서 순차 탐색을 했기 때문에 시간초과 발생 
- 순차 탐색할 때, 배열의 모든 데이터가 담겨 있는 경우(최악의 경우) 오래 걸릴 수 있음 

두 번째의 경우, 딕셔너리만 사용했다. 즉, 해시 테이블만 사용하여 검색을 수행했기 때문에 시간초과가 발생하지 않았다.
- 한 번의 딕셔너리 검색으로 결과를 출력