백준 10815: 숫자 카드 Python

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

10815번: 숫자 카드

 

 

처음에는 아래처럼 단순하게 풀었고, 역시나 시간초과가 나왔다.

in 함수에서 시간이 오래 걸리기 때문에 테스트 케이스 중 큰 값이 있다면 무조건 걸릴 것이다.

import sys
input = sys.stdin.readline

N = int(input())    # N: 숫자 카드의 개수
cards = list(map(int, input().split()))     # 숫자 카드에 적혀있는 정수
M = int(input())    # M: 가지고 있는지 판단할 숫자 카드 수
wants = list(map(int, input().split()))     # 가지고 있는지 판단할 수ㅜㅅ자

for card in wants:
    if card in cards:
        print(1, end=' ')
    else:
        print(0, end=' ')

 

따라서 아래와 같이 -10,000,000부터 10,000,000의 숫자에 대한 배열을 하나 만들었고

존재하는 숫자 카드에 대해서 1로 표시해뒀다.

이후 가지고 있는지 판단할 때는 배열의 해당 칸이 1인지를 기준으로 했다.

import sys
input = sys.stdin.readline

N = int(input())    # N: 숫자 카드의 개수
cards = list(map(int, input().split()))     # 숫자 카드에 적혀있는 정수
M = int(input())    # M: 가지고 있는지 판단할 숫자 카드 수
wants = list(map(int, input().split()))     # 가지고 있는지 판단할 숫자

arr = [0] * 20000001
for i in range(N):
    arr[cards[i]+10000000] = 1

for i in range(M):
    if arr[wants[i]+10000000]:
        print(1, end=' ')
    else:
        print(0, end=' ')