[C++] 백준 12757번: 전설의 JBNU

문제 링크

12757번: 전설의 JBNU

문제 요약

다음의 쿼리를 수행하는 데이터베이스를 구현해야 한다.
1 Key Value : 해당 Key와 Value를 가진 데이터를 추가한다. Key가 이미 존재하는 입력은 주어지지 않는다.
2 Key Value : 해당 Key로 검색된 데이터를 Value로 변경한다. 조건을 만족하는 유일한 Key가 없는 경우 무시한다.
3 Key : 해당 Key로 검색된 데이터를 출력한다. 조건을 만족하는 Key가 없는 경우 -1을 출력한다. 만약 해당하는 Key가 두 개 이상 존재한다면 ?를 출력한다. 모든 출력은 개행을 포함해야 한다

접근 방법

트리맵을 사용해서 풀 수 있습니다. 1번 쿼리는 너무 간단하지만 2번, 3번 쿼리가 조금 까다로운데, 찾고자 하는 키가 없는 경우에는 해당 키와의 차의 절댓값이 K 이하인 가장 가까운 키에 대해서 퀴리를 수행해야 합니다. 키의 범위는 0 이상 10억 이하이기 때문에 순차탐색을 하면 무조건 시간초과를 받을 수밖에 없습니다.

이 문제를 이용하기 위해 map 컨테이너의 멤버함수인 lower_bound를 사용했습니다. 아시다시피 lower_bound는 찾고자하는 값이 있다면 그 위치를 반환하고, 없다면 그보다 큰 가장 작은 값의 위치를 반환합니다.

제 경우에는 multiset에서 lower_bound를 지원하는 사실을 원래 알고 있어서 unordered_map과 multiset을 써보려고 했습니다. 그러다가 혹시나 하고 알아보니 map에도 lower_bound가 멤버함수로 있어서 이를 활용하는 쪽으로 방향을 선회했습니다.

문제는 단순히 이 방법을 이용하는 경우에는 키보다 크거나 같은 가장 작은 키는 찾을 수 있어도, 작거나 같은 가장 큰 키는 찾을 수 없다는 것입니다. 이 때문에 살짝 고민을 했는데, 다익스트라 문제를 풀때, 우선순위큐에서 비교함수를 따로 쓰기 싫은 경우 가중치에 -1을 곱해서 넣는 것처럼, 키를 음수로 변환한 맵을 하나 더 만드는 방법으로 해결했습니다.

아래 코드가 있는데 정리가 덜 되서 살짝 지저분합니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
map<int, int> mp;
map<int, int> mm;

int find_key(int key) {
	auto it1 = mp.lower_bound(key);
	auto it2 = mm.lower_bound(-key);

	if (it1 == mp.end() && it2 == mm.end())
		return -1;
	else if (it1 == mp.end()) {
		pair<int, int> val = *it2;
		val.first *= -1;
		if (abs(val.first - key) > k)
			return -1;
		else
			return val.first;
	}
	else if (it2 == mm.end()) {
		pair<int, int> val = *it1;
		if (abs(val.first - key) > k)
			return -1;
		else
			return val.first;
	}
	else {
		pair<int, int> val1 = *it1;
		pair<int, int> val2 = *it2;
		val2.first *= -1;

		int av1 = abs(val1.first - key), av2 = abs(val2.first - key);

		if (av1 > k && av2 > k)
			return -1;
		else if (val1.first == val2.first)
			return val1.first;
		else if (av1 == av2)
			return -2;
		else if (av1 > av2)
			return val2.first;
		else
			return val1.first;
	}
}

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

	cin >> n >> m >> k;

	while (n--) {
		int key, value;
		cin >> key >> value;
		mp.insert({ key, value });
		mm.insert({ -key, value });
	}

	while (m--) {
		int query, key, value, ret;
		cin >> query;

		switch (query) {
		case 1:
			cin >> key >> value;
			mp.insert({ key, value });
			mm.insert({ -key, value });
			break;
		case 2:
			cin >> key >> value;
			ret = find_key(key);

			if (ret < 0)
				break;

			if (mp.find(ret) != mp.end()) {
				mp[ret] = value;
				mm[-ret] = value;
			}
			break;
		case 3:
			cin >> key;
			ret = find_key(key);

			if (ret == -2)
				cout << "?\n";
			else if(ret == -1)
				cout << -1 << '\n';
			else
				cout << mp[ret] << '\n';
		}
	}

	return 0;
}