BOJ 백준 10816 : 숫자 카드 2

시작하면서

　이번 문제는 이분 탐색(Binary Search) 문제이다. 이전 문제인 숫자 카드 문제의 변형 버전이다.

BOJ 10816 - 숫자 카드 2

​

문제 이해

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

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

​

문제 아이디어

　해당 문제의 이전 숫자 카드 문제에서 2가지 조건이 추가되었다.

1. 시간 제한이 2초 -> 1초로 변경되었다.
2. 각 수가 적힌 숫자 카드를 몇 개 가지고 있는지를 출력해야 한다.

​ 이 조건들을 맞추기 위해서 이전과 다르게 시간도 줄여야한다. 시간을 줄이는 키워드는 “벡터에 동일한 숫자가 있으면 제거해서 이분 탐색 시간을 줄인다” 이다.

​ 조건은 이전과 동일하다.

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

​ 그렇기 때문에 (이분 탐색으로 풀고 싶어서…) 사실 메모리가 넉넉해서 배열을 2000만개 잡으면 더 쉽고 빠르게 풀 수 있다. 하지만 이분 탐색을 공부해야하기도 하고, 메모리를 많이 사용하는 것은 별로 좋아하지 않으므로 이분 탐색으로 해결했다.

​ “벡터에 동일한 숫자가 있으면 제거해서 이분 탐색 시간을 줄인다”를 multiset을 사용했고, 인풋을 받은 후에 새로운 벡터에 숫자와 개수를 pair<int, int>의 형태로 담았다.

​

해결

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

using namespace std;

int GetNumberCountExistInVector(const vector<pair<int, 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].first == number)
            return v[avgNumber].second;

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

        avgNumber = (minNumber + maxNumber) * 0.5;
    }

    return 0;
}

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

    int N, M;
    multiset<int> s;
    vector<pair<int,int>> firstCard;
    vector<int> secondCard;

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

        cin >> card;

        s.insert(card);
    }

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

    int prevNum = -10000001;

    // 1. 카드의 값과 개수를 받아둔 세트를 firstCard 벡터에 초기화해준다.
    for (multiset<int>::iterator iter = s.begin(); iter != s.end(); iter++)
    {
        if (prevNum == *iter)
            continue;

        prevNum = *iter;

        firstCard.push_back(make_pair(*iter, s.count(*iter)));
    }

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

    return 0;
}

​

마치며

　다른 사람들의 코드를 보니 수행 시간이 매우 빨라서 놀랐는데, equl_range를 사용하거나 2000만개의 배열을 사용하는 방법이 대부분이었다. 이분 탐색을 사용하면 내가 해결한 정도의 시간이 나오는게 정상이니 안심한다.