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;
}
Author And Source
이 문제에 관하여(Backjoon_1700_멀티탭 스케쥴링), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soonyubi/Backjoon1700멀티탭-스케쥴링저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)