Backjoon_1700_멀티탭 스케쥴링

1700-멀티탭스케쥴링

문제가 얘기하고자 하는 바는 탭에 꽂혀있는 전자기기 중 다음에 나올 전자기기의 순서를 탭에 꽂혀 있는 전자기기가 알고 있으면 된다.

사용할 전자기기를 입력받은 후 pair<현재전자기기,다음에 나올 현재 전자기기의 index> 의 형태로 데이터를 저장하는 전처리를 진행하였다.
( 전자기기가 뒷순서에 있으면 해당 인덱스를 반환, 없다면 INF반환)

다음에 나올 현재 전자기기의 Index = next_index

각각의 전자기기가 들어올때마다
	만약 탭이 꽉차 있지 않다면
    	탭에 들어오는 전자기기와 꽂혀있는 전자기기가 같다면 
        	탭에 꽂혀있는 전자기기의 next_index를 갱신
        탭에 전자기기를 꽂는다.
    꽉차 있다면
    	만약 꽂혀 있는 전자기기 중 새로 꽂을 전자기기가 겹친다면
        	해당 전자기기의 next_index 갱신
        겹치지 않는다면
        	탭을 next_index의 오름차순으로 정렬
            탭에 마지막에 꽂혀있는 전자기기를 새로 들어올 전자기기와 교체 

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

vector<int> machine;
vector<pair<int, int>> machine_with_priority;
vector<pair<int, int>> tab;

int next_index[100];

int N=0, K=0;
int whatIsNext(int present, int m)
{
	for (int i = present+1; i < K; i++)
	{
		if (m == machine[i])
		{
			return i;
		}
	}
	return 101;
}
bool cmp(pair<int, int> a, pair<int, int> b) { return a.second < b.second; }
int main()
{
	
	int cnt = 0; 
	cin >> N;
	cin.ignore();
	cin >> K;

	
	for(int i=0;i<K;i++)
	{
		int a;
		cin >> a;
		cin.ignore();
		machine.push_back(a);
		next_index[i] = a;
	}

	for (int i = 0; i < K; i++)
	{
		int x = whatIsNext(i, machine[i]);
		
		machine_with_priority.push_back({ machine[i],x});
	}
	/* 확인용 
	for (auto x : machine_with_priority)
	{
		cout << "{ " << x.first << ", " << x.second<< "}\n";
	}
	*/
	bool flag = false;
	bool flag2 = false;
	for (int i = 0; i < K; i++)
	{
		flag = false;
		flag2 = false;
		if (tab.size() != N) // tab이 꽉차 있지 않으면
		{
			for (int t = 0; t < tab.size(); t++)
			{
				if (tab[t].first == machine_with_priority[i].first) 
				{
					tab[t].second = machine_with_priority[i].second;
					flag2 = true;
					break;
				}
			}
			if (!flag2)
			{
				tab.push_back(machine_with_priority[i]);
			}
		}
		else {
			for (int t = 0; t < N; t++)
			{
				if (tab[t].first == machine_with_priority[i].first)
				{
					tab[t].second = machine_with_priority[i].second;
					flag = true;
				}
			}
			if (!flag)
			{
				sort(tab.begin(), tab.end(), cmp);
				tab[N - 1] = machine_with_priority[i];
				cnt++;
			}
		}

	}

	cout << cnt;
}