[BOJ] 10815번 : 숫자 카드

🔒 문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

📚 예제

Ex1)

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

1 0 0 1 1 0 0 1

📌 풀이

1. 리스트 사용

import sys

N = int(sys.stdin.readline())
ary = [int(x) for x in sys.stdin.readline().split()]
M = int(sys.stdin.readline())
find = [int(x) for x in sys.stdin.readline().split()]

for i in find:
    if i in ary:
        print(1,end = ' ')
    else:
        print(0,end = ' ')

=> 시간 초과, 리스트의 경우 시간 복잡도가 O(N)
딕셔너리(시간 복잡도 O(1))를 사용해서 풀어보겠다.

2. ary를 리스트가 아닌 딕셔너리 사용

import sys
from collections import defaultdict
N = int(sys.stdin.readline())
ary = defaultdict(int)
ary = [int(x) for x in sys.stdin.readline().split()]
M = int(sys.stdin.readline())
find = [int(x) for x in sys.stdin.readline().split()]

for i in find:
    if(i in ary):
        print(1, end =' ')
    else:
        print(0, end = ' ')

=> ary를 defaultdic를 사용했는데 둘다 딕셔너리를 사용해야하나 보다. 또 시간 초과가 떴다

슬프다

3. ary랑 find 둘다 딕셔너리 사용

import sys
from collections import defaultdict
N = int(sys.stdin.readline())
ary = defaultdict(int) 
for x in sys.stdin.readline().split():ary[x] = 1
M = int(sys.stdin.readline())
for x in sys.stdin.readline().split():
    print(ary[x],end = ' ')

=> defaultdic을 사용해서 ary값을 받을때 value에 1을 저장하고, 다음에 find 값을 받으면서 바로 print를 하는데,
deaultdic이기 때문에 dic에 없는 값은 자동으로 value가 0이 됨 그렇게 프린트하면 완성

🔑 python 코드

import sys
from collections import defaultdict
N = int(sys.stdin.readline())
ary = defaultdict(int) 
for x in sys.stdin.readline().split():ary[x] = 1
M = int(sys.stdin.readline())
for x in sys.stdin.readline().split():
    print(ary[x],end = ' ')

3번만에 성공,,,