[BOJ 28446 // C++] 볼링공 찾아주기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 28446번 문제인 볼링공 찾아주기이다.
문제는 아래 링크를 확인하자.

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

28446번: 볼링공 찾아주기

 

볼링공의 무게를 key로 갖는 map을 활용하면 문제를 간단히 해결할 수 있다.

 

map을 이용하지 않더라도 offline query 기법을 이용해 문제를 해결할 수도 있다. 구체적으로, 쿼리를 모두 읽어 각 1번 쿼리로부터 알 수 있는 최종적으로 보관중인 모든 볼링공을 무게순으로 먼저 정렬한 다음 각 2번 쿼리에 대한 답을 이진 탐색을 이용해 구해 문제를 해결할 수도 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int Q;
map<int, int> mp;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> Q;
	while (Q--) {
		int q; cin >> q;
		if (q == 1) {
			int x, w; cin >> x >> w;
			mp.insert(make_pair(w, x));
		}
		else {
			int w; cin >> w;
			cout << mp[w] << '\n';
		}
	}
}