[백준/BOJ] 백준 12757번 : 전설의 JBNU

www.acmicpc.net/problem/12757

12757번: 전설의 JBNU

map<int, int> db을 통해 데이터베이스를 표현하고, lower_bound와 upper_bound를 통해 문제를 해결했다.

 

코드

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

int n, m, k;
map<int, int> db;
map<int, int>::iterator it1;
map<int, int>::iterator it2;

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

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++)
	{
		int key, value;
		cin >> key >> value;

		db.insert(make_pair(key, value));
	}

	for (int i = 0; i < m; i++)
	{
		int order;
		int key, value;
		cin >> order;

		if (order == 1)
		{
			cin >> key >> value;

			db.insert(make_pair(key, value));
		}

		else if (order == 2)
		{
			cin >> key >> value;

			it1 = db.lower_bound(key);
			it2 = db.upper_bound(key);

			//해당 키가 있는경우
			if (it1 != db.end() && (*it1).first == key)
				(*it1).second = value;

			//해당 키가 없는 경우
			else
			{
				if (it1 != db.begin())
					it1--;

				if (it2 == db.end())
					it2--;

				//같은것을 찾았을 경우
				if ((*it1).first == (*it2).first)
				{
					if (abs((*it1).first - key) <= k)
						(*it1).second = value;
				}

				else
				{
					//유일한 key가 없는 경우
					if (abs((*it1).first - key) == abs((*it2).first - key))
						continue;

					if (abs((*it1).first - key) < abs((*it2).first - key))
					{
						if (abs((*it1).first - key) <= k)
							(*it1).second = value;
					}

					if (abs((*it1).first - key) > abs((*it2).first - key))
					{
						if (abs((*it2).first - key) <= k)
							(*it2).second = value;
					}
				}
			}
		}

		else if (order == 3)
		{
			cin >> key;

			it1 = db.lower_bound(key);
			it2 = db.upper_bound(key);

			//해당 키가 있는경우
			if (it1 != db.end() && (*it1).first == key)
				cout << (*it1).second << "\n";

			//해당 키가 없는 경우
			else
			{
				if (it1 != db.begin())
					it1--;

				if (it2 == db.end())
					it2--;

				//같은것을 찾았을 경우
				if ((*it1).first == (*it2).first)
				{
					if (abs((*it1).first - key) <= k)
						cout << (*it1).second << "\n";
					else
						cout << -1 << "\n";
				}

				else
				{
					//유일한 key가 없는 경우
					if (abs((*it1).first - key) == abs((*it2).first - key))
					{
						if (abs((*it1).first - key) <= k)
							cout << "?" << "\n";
						else
							cout << -1 << "\n";
					}

					else if (abs((*it1).first - key) < abs((*it2).first - key))
					{
						if (abs((*it1).first - key) <= k)
							cout << (*it1).second << "\n";
						else
							cout << -1 << "\n";
					}

					else if (abs((*it1).first - key) > abs((*it2).first - key))
					{
						if (abs((*it2).first - key) <= k)
							cout << (*it2).second << "\n";
						else
							cout << -1 << "\n";
					}
				}
			}
		}
	}

	return 0;
}