숫자 카드 2 #10816 c++ 풀이

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

10816번: 숫자 카드 2

처음들었던 생각은 부르트 포스로 될까? 하는 생각이었고 결국 천만 * 천만 번의 연산을 수행해야해서 

다른 방법을 사용해야겠다고 생각했습니다.

 

두번째로 생각해낸 방법은 vector에 담아서 수 검색이 안될때까지 bineary_search를 하는 방법을 생각했습니다.

 

세번째로는 그냥 들어오면서 세면 되는거 아냐? 하고 맵을 사용했습니다.

#include <iostream>
#include <map>

using namespace std;

map <int, int> m;
int N, M, card;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> card;
		m[card]++;
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> card;
		cout << m[card] << " ";
	}
}

맞긴 맞았는데, 찜찜해서 

2번째 방법을 알고싶어서 구글링 했습니다.

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

using namespace std;

int n,m;
vector<int> arr;
vector<int> target;

int main() {
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);

    cin >> n;
    int count[n]={0,};
    for(auto i = 0;i<n;i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    sort(arr.begin(),arr.end());

    cin >> m;
    for(auto i =0; i<m;i++) {
        int x;
        cin >> x;

        cout << upper_bound(arr.begin(),arr.end(),x) - lower_bound(arr.begin(),arr.end(),x)<< " ";
    }
}

upper_bound 와 lower_bound라는 것을 사용해서 풀 수 있다고 하는데, 뭔지 모르니 공부해봐야겠습니다.

출처 : https://tooo1.tistory.com/126

[백준(BOJ)] 10816번 : 숫자 카드 2 - C++[CPP]