[백준/BOJ] 백준 1700번 : 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

 멀티탭에서 어떠한 전기제품을 빼야 하는 순간이 올 때 가장 효율적인 것은, 다음에 더 이상 쓰이지 않는 전기제품을 빼는 것이다. 그다음으로 효율적인 것은 다음에 쓰일 순서가 가장 뒤인 것을 빼는 것이다.  그러므로 multitap이라는 이름의 multimap을 만들어 현재 멀티탭에 사용 중인 전기제품의 다음 사용 순서와 이름을 저장하고 전기용품의 다음 사용 순서 기준으로 내림차순 정렬을 하였다 여기서 주의해야 할 점은 다음에 더 이상 쓰이지 않는 전기제품의 다음 사용순서는 매우 큰 수를 저장한다. 이런 방식을 이용하면 멀티탭에서 어떠한 전기제품을 빼야 하는 순간이 올 때, 무조건 multitap.begin()에 있는 전기제품을 빼면 된다. 그리고 각각의 전기제품이 언제 사용되는지를 관리하기 위해 전기제품마다 큐를 만들어서 관리하였다. 또한 주의해야 할 점은 사용하려고 하는 전기제품이 현재 멀티탭에 사용 중일 경우에 플러그를 빼지 않더라도 multitap에서 해당 전기제품의 다음 사용 순서 업데이트와 해당 전기제품의 큐 관리를 위해 같은 제품이라도 multitap에 그 전기제품의 정보를 지우고 새로운 정보를 넣는 과정과, 해당 전기제품의 큐에서 pop 하는 과정이 필요하다.

 

코드

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



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

	int n, k;
	cin >> n >> k;

	//멀티탭에 사용되는 전기용품의 다음 사용 순서,전기용품을 저장할 내림차순 multimap 생성
	multimap <int, int, greater<int>> multitap; 
	multimap <int, int> :: iterator iter;
	//각각 제품이름의 큐 생성
	vector<queue<int>> q (k + 1); 
	//멀티탭에 해당 전기용품이 사용되는지 체크
	vector<bool> multitapcheck(k + 1, false); 
	//사용 순서대로 저장
	vector<int> order;
	//플러그를 빼는 횟수를 저장
	int cnt = 0; 
	int temp;

	for (int i = 0; i < k; i++)
	{
		cin >> temp;
		order.push_back(temp);
		q[temp].push(i+1); //각각 제품이름 큐에 사용 순서를 저장
	}

	for (int i = 0; i < k; i++)
	{
		
		//멀티탭에 order[i]제품이 사용되지 않고 있을때
		if (multitapcheck[order[i]] == false) 
		{
			//멀티탭에 공간이 남았을때 바로 멀티탭을 사용한다
			if (multitap.size() < n) 
			{
				multitapcheck[order[i]] = true;
				//해당 전자기기 큐에서 이번에 사용되는 순서 pop
				q[order[i]].pop();
				
				//multitap에 지금 사용되는 전기용품의 다음 사용 순서, 제품이름을 저장
				
				//이번에 사용되는 전기용품이 다음부터 사용되지 않을때는 다음 순서를 987654321라고 
				//가정해, 다음에 가장먼저 뽑히도록한다
				if (q[order[i]].size() == 0)
				{
					multitap.insert(make_pair(987654321, order[i]));
				}
				else
					multitap.insert(make_pair(q[order[i]].front(), order[i]));
			}

			//멀티탭이 꽉 찼을때(무언가를 빼야될때)
			else 
			{
				//multitap에서 다음 순서가 가장큰 제품을 멀티탭에서 제거한다
				multitapcheck[(*multitap.begin()).second] = false;
				multitap.erase(multitap.begin());

				//order[i] 제품을 멀티탭에서 사용한다
				multitapcheck[order[i]] = true;
				//해당 전자기기 큐에서 이번에 사용되는 순서 pop
				q[order[i]].pop();
				
				//multitap에 지금 사용되는 전자기기의 다음 사용 순서, 제품이름을 저장
				
				//이번에 사용되는 전기용품이 다음부터 사용되지 않을때는 다음 순서를 987654321라고 
				//가정해, 다음에 가장먼저 뽑히도록한다
				if (q[order[i]].size() == 0)
				{
					multitap.insert(make_pair(987654321, order[i]));
				}
				else
					multitap.insert(make_pair(q[order[i]].front(), order[i]));

				cnt++;
			}
		}

		//멀티탭에 order[i]제품이 사용되고 있을때
		else 
		{
			//멀티탭에 order[i]가 어느부분에 사용되고 있는지 찾는다
			for (iter = multitap.begin(); iter != multitap.end(); iter++)
			{
				if ((*iter).second == order[i])
					break;
			}

			//기존 사용되고 있는 전자기기 정보를 최신 정보로 교체한다

			//기존의 정보는 없애고
			multitap.erase(iter);

			//새로운 정보를 넣는다

			//해당 전자기기 큐에서 이번에 사용되는 순서 pop
			q[order[i]].pop();

			//multitap에 지금 사용되는 전자기기의 다음 사용 순서, 제품이름을 저장

			//이번에 사용되는 전기용품이 다음부터 사용되지 않을때는 다음 순서를 987654321라고 
			//가정해, 다음에 가장먼저 뽑히도록한다
			if (q[order[i]].size() == 0)
			{
				multitap.insert(make_pair(987654321, order[i]));
			}
			else
				multitap.insert(make_pair(q[order[i]].front(), order[i]));

		}
	}


	cout << cnt;

	return 0;
}