백준 1700 - 멀티탭 스케줄링

문제링크

• 백준 1700

문제설명

• 첫째줄에 멀티탭 구멍의 개수 N 과 전기 용품의 총 사용횟수 K 가 주어진다.
• 다음 줄에 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다.
• 전기 용품은 멀티탭에 연결하여 사용하여야 하는데, 플러그를 빼는 횟수를 최소화하는 프로그램을 구현하라.

문제접근

• 전기용품의 사용 순서를 알고 있기 때문에 그리디 알고리즘 으로 해결할 수 있다.
• 각 전기용품이 사용되는 시점을 인접리스트로 관리한다.
• 현재 전기용품을 멀티탭에 꽂을 수 있는지 판단하는 방법은 아래와 같다.
  1. 멀티탭에 여분의 공간이 있다면 꽂는다.
  2. 멀티탭에 여분의 공간이 없다면 다음과 같은 우선 순위에 따라 전기용품 플러그를 제거한다.
  • 나중에 사용하지 않는 전기용품이 있다면 해당 전기용품의 플러그를 제거한다.
  • 멀티탭에 꽂힌 모든 전기용품이 나중에 사용해야 한다면 가장 늦게 사용되는 전기용품의 플러그를 제거한다.

구현

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

int N, K;
vector<int> devices; // 전기용품 순서를 담는다.
vector<int> timeTable[101]; // 각 전기용품을 사용하는 시간 정보를 담는다.
vector<int> multitapStatus;

int getNextUseDevice()
{
	priority_queue<pair<int, int>> pq; // deafult: max heap
	for (int i = 0; i < multitapStatus.size(); i++)
	{
		int curDevice = multitapStatus[i];
		if (timeTable[curDevice].size() > 0)
		{
			pq.push(make_pair(timeTable[curDevice][0], i));
		}
		else if (timeTable[curDevice].size() == 0)
		{
			return i; // 등장하지 않는 전기용품은 바로 뽑는다.
		}
	}

	// 모든 전기용품이 뒤에 사용되는 경우
	return pq.top().second; // 가장 늦게 사용하는 전기용품이 꽂혀 있는 인덱스를 반환
}

bool checkMultiTap(int curDevice)
{
	if (find(multitapStatus.begin(), multitapStatus.end(), curDevice) != multitapStatus.end()) return true;
	else  return false;
}

int solution()
{
	int removeCount = 0;
	for (int time = 0; time < K; time++)
	{
		int curDevice = devices[time];
		timeTable[curDevice].erase(timeTable[curDevice].begin());
		if (checkMultiTap(curDevice)) continue;
		if (multitapStatus.size() == N)
		{
			int removeDeviceIdx = getNextUseDevice();
			multitapStatus.erase(multitapStatus.begin() + removeDeviceIdx);
			removeCount++;
		}
		multitapStatus.push_back(curDevice);
	}
	return removeCount;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> N >> K;
	for (int i = 0; i < K; i++)
	{
		int product;
		cin >> product;
		devices.push_back(product);
		timeTable[product].push_back(i);
	}
	int ans = solution();
	cout << ans << endl;
}