10815번-숫자 카드

문제

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

10815번: 숫자 카드

---

접근방법

1) 접근 사고

n의 카드들이 있을때 m의 카드들이 n의 카드들에도 있는지도 확인하면 되는 문제였습니다. 이진 탐색을 활용하면 쉽게 해결할 수 있는 문제 입니다.

 

2) 시간 복잡도

n과 m의 카드의 길이가 500,000이므로 완전탐색을 돌리면 25,000,000,000,000의 연산이 일어나므로 시간복잡도를 줄여야 하는 문제였습니다.

 

3) 배운 점

두 가지 방식으로 문제를 해결할 수 있다 생각했습니다. 첫 번째는 binary_search를 활용한 이진 탐색이고 두 번째는 lower_bound, upper_bound를 활용한 equal_lange를 사용해서 두 리턴값의 차이로 구하는 방법입니다. 두 방식으로 전부 구현해 보았습니다.

 

4) PS

paramatric search를 활용해서 풀어도 되진만 STL을 활용하면 더욱 코드가 간결해진다!

---

정답 코드

1.binary_search를 활용한 구현 코드

#include<bits/stdc++.h>
#define pill pair<int,int>
#define mp(X,Y) make_pair(X,Y)
 
using namespace std;
const int MAX = 1e7;
 
int n,m;
int arr[MAX];
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    sort(arr, arr + n);
 
    cin >> m;
 
    for (int i = 0; i < m; i++)
    {
        int num;
        cin >> num;
 
        if (binary_search(arr, arr + n, num))
            cout << 1 << "\n";
        else
            cout << 0 << "\n";
    }
 
    return 0;
}
 
 

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 5e5 + 1;
int arr1[MAX];
int arr2[MAX];
 
int n, m;
int main(void)
{
    fastio;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr1[i];
    cin >> m;
    for(int j = 0; j < m; j++)
        cin >> arr2[j];
    sort(arr1, arr1 + MAX);
    for(int i = 0; i < m; i++)
    {
        auto[lo, hi] = equal_range(arr1, arr1 + MAX, arr2[i]);
        cout << hi - lo << "\n";
    }
}