BOJ 백준 10815 : 숫자 카드

시작하면서

　이번 문제는 이분 탐색(Binary Search) 문제이다. 이분 탐색 알고리즘에 약해서 쉬운 문제부터 하나 풀어봤다.

BOJ 10815 - 숫자 카드

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 4가지이다.

• N, M : 카드의 개수
• card vector : A, B

​

문제 아이디어

　해당 문제의 핵심 포인트는 동일한 숫자를 찾아야한다는 것이다.

1. 완전 탐색을 사용한다고 하면 최악의 경우인 500,000 * 500,000 = 250,000,000,000에서 시간 초과가 발생한다.

2. 배열을 사용해 있는지 없는지의 여부를 검사한다고 하면 -10,000,000 ~ 10,000,000의 범위라서 메모리 초과가 발생한다.

   정정한다. 메모리 초과 발생 안 한다. 메모리 제한 : 256MB = 256,000,000 / 20,000,002 * 8 = 160,000,016

3. 해시 테이블을 사용한다고 해도 최대 500,000이므로 메모리 초과가 발생한다.

   정정한다. 메모리 초과 발생 안 한다. 메모리 제한 : 256MB = 256,000,000 / 500,000 * 8 = 4,000,000

​ 그렇기 때문에 (이분 탐색으로 풀고 싶어서…) 이 문제는 하나를 검사할 때마다 직접 찾아줘야하고, 검색 중에서 시간이 빠른 이분 탐색을 사용해서 해결해야한다. 이분 탐색은 O(logn)의 성능을 보이므로 한번 검색에 약 log(500,000) = 5.698…이므로 시간 초과가 발생하지 않을 것이다.

​

해결

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool IsNumberExistInVector(const vector<int>& v, const int number)
{
    int minNumber = 0, maxNumber = 0, avgNumber = 0;

    maxNumber = v.size() - 1;
    avgNumber = (minNumber + maxNumber) * 0.5;

    while (minNumber <= maxNumber)
    {
        if (v[avgNumber] == number)
            return true;

        if (v[avgNumber] > number)
        {
            maxNumber = avgNumber - 1;
        }
        else
        {
            minNumber = avgNumber + 1;
        }

        avgNumber = (minNumber + maxNumber) * 0.5;
    }

    return false;
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    int N, M;
    vector<int> firstCard;
    vector<int> secondCard;

    cin >> N;
    firstCard.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> firstCard[i];
    }

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

    // 1. 오름차순으로 기준이 되는 첫번째 카드 벡터들을 정렬해준다.
    sort(firstCard.begin(), firstCard.end(), less<>());

    // 2. secondCard의 각 값을 기준으로 firstCard에서 이분탐색을 통해 값이 있는지 찾는다.
    for (int i = 0; i < secondCard.size(); i++)
    {
        if (IsNumberExistInVector(firstCard, secondCard[i]) == true)
        {
            cout << "1 ";
        }
        else
        {
            cout << "0 ";
        }
    }

	return 0;
}

​

마치며

　이상하게 예전부터 이분 탐색이 머리에 잘 박히지 않는다. 이렇게 문제를 풀고도 나중에 가면 기억이 안 날수도 있으니 반복해서 문제를 풀어봐야겠다.