10816 숫자 카드 2

입력값 사이즈 보니깐 count 배열 따로 둬서 풀 수 있을 것 같은데 map을 쓰고 싶어서 map 사용해서 풀었더니 에러가 났다.......... 시간 복잡도 생각해봐도 map은 tree형태니깐 logN 입력값 한번 할 때마다 map 확인하니깐 NlogN이 걸릴텐데 왜 터지지 싶었음. 알고보니 map이 좀 느린 애라 그렇다고 합니다.. 허잉

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;



int     main()
{
	int n;
	scanf("%d", &n);

	map<int, int> mp;

	for (int i = 0; i < n; i++)
	{
		int n;
		scanf("%d", &n);

		mp[n]++;
	}

	int m;
	scanf("%d", &m);
	for (int i = 0; i < m; i++)
	{
		int n;
		scanf("%d", &n);

		printf("%d ", mp[n]);
	}

	
	return 0;
}

 

그래서 다시 count 배열 사용해서 풀었다. 

아 처음에 배열 크기만 생각해서 500,000으로 해서 틀렸고 다음으로 음수값 고려해서 풀었다. 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int countv[20000005];

int     main()
{
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		int n;
		scanf("%d", &n);

		countv[n + 10000000]++;
	}

	int m;
	scanf("%d", &m);
	for (int i = 0; i < m; i++)
	{
		int n;
		scanf("%d", &n);

		printf("%d ", countv[n + 10000000]);
	}

	
	return 0;
}

 

이제 upper_bound, lower_bound로 풀기

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int countv[20000005];

int     main()
{
	int n;
	scanf("%d", &n);

	vector<int> v(n);
	for (int i = 0; i < n; i++)
		scanf("%d", &v[i]);

	sort(all(v));

	int m;
	scanf("%d", &m);
	for (int i = 0; i < m; i++)
	{
		int n;
		scanf("%d", &n);

		printf("%d ", upper_bound(all(v), n) - lower_bound(all(v), n));
	}

	
	return 0;
}