[백준] 10815번 숫자 카드

문제

https://www.acmicpc.net/problem/10815

풀이과정

하나의 카드뭉치와 카드뭉치 속 카드들의 숫자가 주어진다. 그리고 또 다른 입력으로 숫자들이 들어오고 그 숫자들이 카드뭉치에 있는지 없는지 판단해서 출력하는 문제이다. 이 문제는 이진탐색으로 풀어야되는 문제이다. 이진탐색 구현은 쉽게 했지만 이상하게 시간초과가 나서 당황했었다. 이진탐색을 해서 숫자가 존재하면 cout << “1”; 없으면 cout << “0”; 이런식으로 구현을 했다가 시간초과가 나는걸 보고 따로 ans 배열을 만들어서 나중에 출력하는 식으로 했는데 맞았다. 왜 시간초과가 낫을까 확인해보니 cout과 printf의 속도 차이 같다. 검색해보니 sync_with_stdio(false)를 해도 printf가 더 빠를 수 있다고 했다.

cin과 cout 사용하는게 편해서 사용하고 있었는데 이런식으로 시간초과가 나니까 짜증난다 후

아 그리고 c++에서는 binary_search() 라는 함수로 이진탐색을 제공한다.

하.. 입력을 따로받고 밑에서 다른 for문으로 cout 출력하니까 시간이 printf 쓸 때랑 똑같이 나왔다.

소스코드

// printf 사용
#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_N 500001

int N, M;
int card[MAX_N];


bool Binary_search(int target)
{
    int left, right;

    left = 0; right = N - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (card[mid] < target) left = mid + 1;
        else if (card[mid] > target) right = mid - 1;
        else if (card[mid] == target) return true;
    }

    return false;
}

int main()
{
    ios::sync_with_stdio(false);

    cin >> N;

    for (int i = 0; i < N; i++) cin >> card[i];

    sort(card, card + N);

    cin >> M;

    for (int i = 0; i < M; i++)
    {
        int target;

        cin >> target;

        if (Binary_search(target)) printf("1");
        else printf("0");

        if (i != M - 1) printf(" ");
    }

    return 0;
}

// cout 사용
#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_N 500001

int N,M;
int card[MAX_N];
int target[MAX_N];


bool Binary_search(int target)
{
    int left, right;

    left = 0; right = N - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (card[mid] < target) left = mid + 1;
        else if (card[mid] > target) right = mid - 1;
        else if (card[mid] == target) return true;
    }

    return false;
}

int main()
{
    ios::sync_with_stdio(false);

    cin >> N;

    for (int i = 0; i < N; i++) cin >> card[i];

    sort(card, card + N);

    cin >> M;

    for (int i = 0; i < M; i++)
    {
        cin >> target[i];
    }

    for(int i=0;i<M;i++)
    {
        if (Binary_search(target[i])) cout << "1 ";
        else cout << "0 ";
    }

    return 0;
}