BOJ 백준온라인져지 10815 숫자 카드 풀이

문제 설명

1. Mi 의 숫자가 N 에 존재하는지 출력하는 문제

풀이

1. 이분탐색을 사용하라고 문제 분류가 돼있지만, 더 빠른 풀이를 위해 BitSet 을 사용했다.

2. 이분탐색을 사용하면 O(MlgN + NlgN) 정렬하고 찾는 시간이고, BitSet 을 사용하면(N+M) 이다.

3. 메모리 제한도 높고, Mi 의 제한도 높지 않아서 쉽게 풀 수 있었다.

4. JAVA 로 약 680MS 로 정답이니 거의 엄청 빠른 퍼포먼스를 낼 수 있었다. (첫 제출은 790MS 정도였다. 이유는 숫자 + 문자열을 write 해줬기 때문이다. 변경된 것은 문자열로만 되게)

코드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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을 공백으로 구분해 출력한다.

예제 입력 1 

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

예제 출력 1 

1 0 0 1 1 0 0 1

출처