10816번-숫자카드2

문제

https://www.acmicpc.net/status?user_id=skaguq4270&problem_id=10816&from_mine=1 

채점 현황

---

접근방법

1) 접근 사고

https://hyeophyeop.tistory.com/18 문제와 같습니다. 다만 갯수를 추가 해줘야 하므로 equal_range방식 또는 단순 구현으로 풀이를 해야한다.

 

2) 시간 복잡도

https://hyeophyeop.tistory.com/18 참조

 

3) 배운 점

복습하는데 좋았다!

 

4) PS

3가지 방법으로 구현해보았습니다. equal_range로 구현할 때 이유는 모르겠으나 배열을 사용하여 연산하니 오답처리를 받아서 Vector를 활용하는 방법으로 변경했습니다. 아무래도 메모리를 확보하고 0으로 채워진 영역에서 탐색을 하다보니 오류가 생긴거 같다고 추정하여 필요한 공간만 확보하는 방식으로 변경하였습니다.

---

정답 코드

1.binary_search 구현

#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 n, m;
int arr1[MAX];
int arr2[MAX];
map<int,int> board;
 
int main(void)
{
    fastio;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> arr1[i];
        board[arr1[i]]++;
    }
 
    cin >> m;
    for(int i = 0; i < m; i++)
        cin >> arr2[i];
 
    sort(arr1, arr1 + MAX);
    for(int i = 0; i < m; i++)
    {
        if(binary_search(arr1, arr1 +MAX, arr2[i]))
        {
            cout << board[arr2[i]] <<" ";
        }
        else
            cout <<"0 ";
    }
 
 
}
 

#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;
long long arr[MAX * 2 + 1];
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        arr[num + MAX]++;
    }
 
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int num;
        cin >> num;
        cout << arr[num + MAX] << " ";
    }
 
}
 

#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;
int n, m;
vector<int> v;
 
int main(void)
{
    fastio;
    cin >> n;
    v.resize(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];
 
    cin >> m;
    sort(v.begin(), v.end());
    for(int i = 0; i < m; i++)
    {
        int num;
        cin >> num;
        auto[left, right] = equal_range(v.begin(), v.end(), num);
        cout << right - left << " ";
    }
}