#10816 숫자 카드 2

# 문제

# 입력 및 출력

# 풀이

모르고 문제풀기전에 알고리즘 분류를 봐버렸다ㅋㅋㅋ

이분탐색 쓰라길래 이분탐색으로 어떻게 구현하지 했는데 도저히 모르겠어서 map을 사용했다

#include <iostream>
#include <map>
using namespace std;
map<int, int> card;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m, t;
	cin >> n;
	while (n--) {
		cin >> t;
		card[t] += 1;
	}
	cin >> m;
	while (m--) {
		cin >> t;
		if (card.find(t) != card.end()) cout << card[t] << " ";
		else cout << 0 << " ";
	}
}

처음에 시간초과가 떠서 sync_with_studio, tie를 적어줬더니 해결됐다

 

다른 사람 코드를 보려고 하다가 메모리를 적게 쓰는 코드를 발견했다

lower_bound, upper_bound함수를 사용하는 것이다

이것때문에 이분탐색 분류가 들어가있었던 것 같다ㅋㅋ

 

lower_bound, upper_bound 함수 참고

https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m, t;
	cin >> n;
	while (n--) {
		cin >> t;
		card.push_back(t);
	}
	sort(card.begin(), card.end());
	cin >> m;
	while (m--) {
		cin >> t;
		int lb = lower_bound(card.begin(), card.end(), t) - card.begin();
		int ub = upper_bound(card.begin(), card.end(), t) - card.begin();
		cout << ub - lb << " ";
	}
}

이분탐색이라 그런지 확실히 시간이 적게 걸리긴한다,,,