[백준 10815번 숫자카드/ C++]

www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

알고리즘 분류는 이분탐색과 정렬이었다. 문제에서는 이분 탐색을 사용하여 문제를 해결하길 원했지만, ***counting sort***로 문제를 순식간에 해결할 수 있어서 이를 사용하여 문제를 해결하였다.

 

#include <iostream>
#include <vector>

    using namespace std;
bool num[20000001];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    int in;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> in;
        num[in + 10000000] = true;
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> in;
        cout << ((num[in + 10000000]) ? 1 : 0) << " ";
    }

    return 0;
}

 

문제에서는 숫자카드를 가지고 있는지 안가지고 있는지에 대해서만 1,0으로 출력을 해주는 것을 요구하고 있었기 때문에 배열을 bool로 선언해도 된다고 판단하였다.

 

숫자카드의 범위는 -10,000,000~10,000,000이기 때문에 인덱스를 활용하기 위해서는 input을 받고 +10,000,000를 해주어야 했다.

그렇게 인풋을 받고 해당 index를 true로 변경해주는 작업후에 testcase를 input으로 받고 해당 숫자가 true인지 확인한 후 1혹은 0을 출력해주면 됐다.