21939 백준

문제 추천 시스템 Version 1

 

 

 

처음엔 아무생각없이 Map두개를 사용하여 풀었다.

맵이 알아서 정렬되고, 시간복잡도가 log N이여서 이정도면 시간초과 안나올줄 알았는데 나왔다.

그래서 자세히 살펴보니

N과 P가 10만까지고 입력받는것도 1만이여서

찾는코드가 많아서 찾다가 시간초과가 나는것으로 알고, 최대한 찾는 방법을 줄이는 방법을 고민했다.

 

 

시간초과 난 코드 (무지성 Map사용)

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
using namespace std;
void oneoneoneone()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}
int N, M;
map<int, int> problemmap;
map<int, map<int, int>> level_map;
int main()
{
	oneoneoneone();
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		int num, level;
		cin >> num >> level;
		problemmap.insert({ num,level });
		if (level_map.find(level) == level_map.end())
		{
			map<int,int>mmap;
			mmap.insert({ num,0 });
			level_map.insert({ level, mmap });
		}
		else
		{
			level_map.find(level)->second.insert({ num,0 });
		}
	}

	cin >> M;
	
	for (int i = 0; i < M; ++i)
	{
		string str;
		cin >> str;
		if (str == "recommend")
		{
			int one;
			cin >> one;
			if (one == 1)
			{
				auto iter = (--level_map.end())->second.end();
				iter--;
				cout << iter->first << '\n';
			}
			else if (one == -1)
			{
				cout << level_map.begin()->second.begin()->first << '\n';
			}
		}
		else if (str == "solved")
		{

			int num;
			cin >> num;
			auto iter = problemmap.find(num);

			auto& veciter=level_map.find(iter->second)->second;
			auto veciterbegin = veciter.begin();
			auto veciterend=veciter.end();
			for (; veciterbegin != veciterend; veciterbegin++)
			{
				if (veciterbegin->first == num) {
					veciter.erase(veciterbegin);
					break;
				}
			}
			if (veciter.empty())
				level_map.erase(level_map.find(iter->second));
			problemmap.erase(problemmap.find(num));


		}
		else if (str == "add")
		{
			int num, level;
			cin >> num>>level;
			problemmap.insert({ num,level });
			if (level_map.find(level) == level_map.end())
			{
				map<int, int>mmap;
				mmap.insert({ num,0 });
				level_map.insert({ level, mmap });
			}
			else
			{
				level_map.find(level)->second.insert({ num,0 });
			}
		}
	}
}

 

 

그래서 지울때만 map을 사용하고, priority_queue을 두개 사용해서 min max값을 따로 저장해서

지울때 두번 카운트를 줘서 max지웠을때 한카운트 min에서 지웠을때 한카운트 해서 2카운트되면 맵에서 지워지게끔 했다.

 

통과

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

void oneoneoneone()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}
int N, M;
priority_queue<pair<int, int>>minq , maxq;
map<int, int> deletenum;
int main()
{
	oneoneoneone();
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		int num, level;
		cin >> num >> level;
		maxq.push(make_pair(level, num));
		minq.push(make_pair(-level, -num));
	}

	cin >> M;

	for (int i = 0; i < M; ++i)
	{
		string str;
		cin >> str;
		if (str == "recommend")
		{
			int one;
			cin >> one;
			if (one == 1)
			{
				for (;;)
				{

					int level = maxq.top().first;
					int num = maxq.top().second;
					
					auto finditer = deletenum.find(num);
					if (finditer == deletenum.end())
					{
						cout << num << '\n';
						break;
					}
					else
					{
						finditer->second++;
						if (finditer->second == 2)
							deletenum.erase(finditer);
						maxq.pop();
					}
				}


			}
			else if (one == -1)
			{
				for (;;)
				{

					int level = -minq.top().first;
					int num = -minq.top().second;
					auto finditer = deletenum.find(num);
					if (finditer == deletenum.end())
					{
						cout << num << '\n';
						break;
					}
					else
					{
						finditer->second++;
						if (finditer->second == 2)
							deletenum.erase(finditer);
						minq.pop();
					}
				}
			}
		}
		else if (str == "solved")
		{

			int num;
			cin >> num;
			deletenum.insert({ num,0 });



		}
		else if (str == "add")
		{
			int num, level;
			cin >> num >> level;
			minq.push(make_pair(-level, -num));
			maxq.push(make_pair(level, num));
		}
	}
}