BOJ 10815 숫자 카드(C++)

숫자 카드 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	2838	1162	870	41.409%

문제

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

예제 입력 

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

예제 출력 

1 0 0 1 1 0 0 1

힌트

출처

• 문제를 만든 사람: baekjoon
• 문제의 오타를 찾은 사람: lety mystika

알고리즘 분류

• 이분 탐색

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

#include    <stdio.h> #include    <vector> #include    <algorithm> #pragma warning(disable : 4996)   static std::vector<int> C; static int F[555555]; static int N, M; void bs(int loc) {     int left = 0, right = N-1;     int mid;       while (left <= right)     {         mid = (left + right) / 2;         if (loc > C[mid])             left = mid + 1;         else if (loc < C[mid])             right = mid - 1;         else         {             printf("1 ");             return;         }     }     printf("0 ");     return; } int main() {     int c;     scanf("%d", &N);     for (int i = 1; i <= N; ++i)     {         scanf("%d", &c);         C.push_back(c);     }     sort(C.begin(), C.end());     scanf("%d", &M);     for (int i = 1; i <= M; ++i)         scanf("%d", &F[i]);       for (int i = 1; i <= M; ++i)         bs(F[i]);       return 0; }

이분 탐색(binary search)의 전형적인 문제. 

이분 탐색을 위해서는 정렬된 배열이 필수조건이기 때문에 vector(java에서는 arraylist로 하면 될 것 같다..)로 입력받아 정렬 후 탐색하였다. 

대표적으로 재귀적 방식과 반복적 방식 두가지 모두 사용되는데 둘다 구현하기에 어렵지는 않다. 여기서는 반복적인 방식을 사용하였다.