백준 2776 - 암기왕(C++)

문제 https://www.acmicpc.net/problem/2776

2776번: 암기왕

풀이

입력된 배열에서 특정 값을 찾아내는 문제이므로 이분 탐색을 이용해서 풀면 된다. 

주의할 점은, 탐색해야 할 배열에서 중복 값이 없다는 조건은 없으므로 중복을 제거해줘야 하고,

테스트 케이스마다 수첩 1의 숫자들을 저장할 벡터 v를 초기화해줘야 한다. 이 과정이 없으면 이전 테스트케이스 뒤에 숫자가 추가된다.

 

이분 탐색을 코드로 구현해줘도 되고, 중복 제거를 위해 map이나 set을 이용해도 되는데 후자가 코드는 간결하지만 속도는 이분 탐색을 직접 구현한 코드가 제일 빨랐다. 이분 탐색은 탐색하는 배열을 반씩 줄여나가지만, map이나 set에서 find로 찾는 것은 처음부터 하나하나 확인하기 때문인 듯하다.

 

코드

- 이분 탐색 직접 구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    for(int i=0; i<t; i++)
    {
        vector<int> v; //테스트 케이스마다 벡터가 초기화되어야 하므로
        int n;
        cin>>n;
        for(int j=0; j<n; j++)
        {
            int na;
            cin>>na;
            v.push_back(na);
        }
        v.erase(unique(v.begin(),v.end()),v.end()); //이분탐색은 중복이 없어야 함
        sort(v.begin(),v.end());
        int m;
        cin>>m;
        for(int j=0; j<m; j++)
        {
            int mb;
            cin>>mb;
            int flag = 0;
            int left = 0;
            int right = v.size()-1;
            while(right>=left) //이분 탐색
            {
                int mid = (left+right)/2;
                if(v[mid]==mb)
                {
                    flag=1;
                    cout<<"1 ";
                    break;
                }
                else if(mb>v[mid]) left=mid+1;
                else if(mb<v[mid]) right=mid-1;
            }
            if(flag==0) cout<<"0 ";
        }
    }
}

이분 탐색 코드 수행 결과

- set으로 구현

#include <iostream>
#include <set>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    for(int i=0; i<t; i++)
    {
        set<int> m;
        int n;
        cin>>n;
        for(int j=0; j<n; j++)
        {
            int a;
            cin>>a;
            m.insert(a);
        }
        int k;
        cin>>k;
        for(int j=0; j<k; j++)
        {
            int b;
            cin>>b;
            if(auto it=m.find(b)!=m.end()) cout<<"1"<<'\n';
            else cout<<"0"<<'\n';
        }
    }
}

set 이용 코드 결과