10815_숫자 카드(Cards) with Set and Map

2023.01.24

 

0. Background

This problem has been assigned in Set and Map category. I would like to explore those with this problem.

 

1. Set

1-1. What is Set?

Accodring to the official document, it is explain that Set is used to store multiple items in a single valiable.

This line doesn't seem to make any difference from other types of variable such as list, tuple, and dictionary.

But its characteristics do make difference.

1-2. Characteristic

• Unchangable: The items of set cannot be changed. They can only be removed and added.
• Unordered: There is no concept of order in set.
• Unindexed: Set does not have indexes.
• Unable to duplicate: The most importantly, It cannot have redundant data. Each item in a set has to be distinct.

1-3. Where to use it

Set is useful to perform common math operations like unions and intersections.

 

2. Map

1-1. What is Map?

In the problems of the category, map means Hashmap. In Python, dictionary plays roles as Hashmap. It has two things called key and value. You can get a value that is matched to the key for it.

1-2. Characteristic

Dictionary's characteristics are like below.

• Changable
• Ordered: In after version of 3.6, it is ordered. 
• Unable to duplicate

1-3. Where to use it

When unique keys are available and quick searches are needed, Hashmap(Dictionary in Python) can be used.

 

3. Problem

As the original page does not have translated version for this problem, I would like to make it on this page.

Sanggeon has cards. Each card has an integer written on. He's got N number of cards. When M number of integers are given, find out whether he has them or not.

Input
The first line of input contains N(1≤ N ≤ 500,000), the number of cards that Sanggeon's got. The second line contains N numbers that are on the cards. Each number is bigger or the same than -10,000,000 and smaller or the same than 10,000,000. Each card has a different number. The third line of input contains M(1 ≤ M ≤ 500,000). The last line contains M number of integers(bigger or the same than -10,000,000 and smaller or the same than 10,000,000 )for you to see if he has the cards of separated by spaces. 

Output
For M number of integers, if Sanggeon has the card, print 1, if not, print 1, with separation by spaces.

Example Input

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

Example Output

1 0 0 1 1 0 0 1​

 

4. Solution Code

n = int(input())
cards = list(map(int, input().split(" ")))
m = int(input())
nums = list(map(int, input().split(" ")))

dc = {}
dn = {}

for i in cards:
    dc[i] = 1
for i in nums:
    dn[i] = 0

for i in dn.keys():
    try:
        dc[i]
        dn[i] = 1
    except:
        continue

for i in dn.values():
    print(i, end=" ")