BOJ 10815 : 숫자 카드

문제

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

풀이

1. 시간복잡도 O(N)의 형태로 풀게 되면 시간 초과
2. 이분 탐색 알고리즘을 사용해서 풀어야 하거나, 시간 복잡도가 \( O(log 2^N)) \
   https://satisfactoryplace.tistory.com/39
3. Dictionary 자료형을 이용하면 시간 단축이 가능해서 / 이분 탐색 알고리즘을 사용 할 필요가 없음.
   https://stackoverflow.com/questions/513882/python-list-vs-dict-for-look-up-table

[알고리즘] 이분 탐색(Binaray Search)

Python: List vs Dict for look up table

 

import sys

if __name__ == '__main__':
    M = int(sys.stdin.readline())

    data = list(map(int, sys.stdin.readline().split()))
    
    M2 = int(sys.stdin.readline())

    data2 = list(map(int, sys.stdin.readline().split()))

    dict1 = {data2[i] : 0 for i in range(len(data2))}

    for i in range(M):
        if data[i] in dict1.keys():
            dict1[data[i]] += 1
            
    print(" ".join(map(str, list(dict1.values())))) # 출력 방식 습득:컴프리핸션을 사용할 필요가 없음.