2776. [Python]암기왕

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 256MB
• 딕셔너리

 

3. 파이썬 코드

 

import sys
# 많은 인풋처리
T = int(sys.stdin.readline())
# 테스트 케이스 반복문
for i in range(1,T+1):
	# 딕셔너리 선언
    num_dict = {}
    N = int(sys.stdin.readline())
    nums = list(map(int,sys.stdin.readline().split()))
    M = int(sys.stdin.readline())
    nums_check = list(map(int,sys.stdin.readline().split()))
    # 딕셔너리에 값 저장
    for j in nums:
        if j not in num_dict:
            num_dict[j] = 0
	# 숫자가 딕셔너리에 있으면 1 출력 없으면 0 출력
    for k in nums_check:
        if k in num_dict:
            print('1')
        else:
            print('0')

 

4. 문제를 풀고난 후 생각

 

• 첫 문제 접근을 이분 탐색으로 진행했지만 시간초과가 발생하여 고민한 문제이다. 1,000,000 의 N, M 이기 때문에 결국 리스트를 정렬 후 탐색을 함에 있어서 시간초과가 발생한 것 같다.
• 다른 자료구조인 딕셔너리의 탐색을 통해서 (O(1)) 시간 복잡도를 단순하게 만들었기 때문에 별도의 sort 처리가 필요없고 시간복잡도를 줄이는 방식을 사용하여 체크를 진행했다.
• 시간복잡도에 대해서 고민을 할 수 있던 문제였다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 딕셔너리