[TIL/크래프톤 정글9기] 18일차(숫자 카드)

숫자 카드를 처음 풀땐 시간초과가 나와서 다른 방식으로 하니깐 통과가 됐다. 이번에 해당 내용을 정리해보려한다.

시간 초과 발생

dic = {}
for i in check_card:
    if i in card:
        dic[i] = 1
    else:
        dic[i] = 0

이 코드는 check_card의 각 숫자마다 card 리스트 전체를 검색
리스트는 탐색할 때마다 O(N) 시간 소요
그래서 전체 시간 복잡도는 O(N * M) 이 되어, 입력이 클 경우 시간 초과가 발생

핵심 아이디어
check_card에 있는 숫자들만 딕셔너리에 key로 넣어두고,
card를 돌면서 그 값이 딕셔너리에 있으면 1로 바꾸기
딕셔너리는 key 조회가 평균 O(1)이라 빠름

정리
리스트에서 in 연산은 선형 탐색 → 입력 크면 시간 초과
딕셔너리는 해시 기반 → 탐색이 평균 O(1)
존재 여부 확인 문제는 딕셔너리 사용이 효율적

import sys
input = sys.stdin.readline

n = int(input().rstrip())     # n 값 입력
card = list(map(int, input().rstrip().split())) # 카드 리스트
m = int(input().rstrip())     # 값 입력
check_card = list(map(int, input().rstrip().split())) # 체크 카드 리스트

dic = {}  # 딕셔너리 선언

# 이건 왜 시간초과 나는지 모름 
# for i in check_card:
#     if i in card:
#         dic[i] = 1
#     else:
#         dic[i] = 0

# 체크카드에 있는 카드들 순서대로 딕셔너리 0으로 선언
for i in check_card:
    dic[i] = 0

# 카드리스트를 가져와서 해당 카드가 딕셔너리에 있으면 값을 1로 변경
for j in card:
    if j in dic:
        dic[j] = 1

# print(dic)
# print(dic[10])

# 딕셔너리에 있는 카드들의 값들만 출력
for k in check_card:
    print(dic[k], end=' ')