1700 멀티탭 스케줄링

1700. 멀티탭 스케줄링 / c++ / Gold 1 / 40분

문제

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

1. 멀티탭 구 수인 N과, 꽂아야할 플러그 갯수인 K가 주어진다.
2. 플러그를 뽑고 다시 꽂는 횟수를 최소하 하면 몇번일까?

접근 방식

그리디

1. 처음엔 몇번 더 꽂아야하는지 (뒤에 얼마나 많이 꽂을 필요가 있는지)로 확인하려고 했다.
2. 그런데 생각해보니, 1번3번이 있을 때 뒤에 아무리 많이 3번을 꽂더라도, 당장 내가 다음에 필요한게 1번이면, 1번을 놔두고 3번을 빼는게 더 합리적인 것 같았다.
3. 그래서 ‘더 가까운 시간에 필요한’ 것을 기준으로 정렬하기로 했다.
4. 만약 이후로 더 이상 꽂을 필요가 없다면 그걸 빼기로 하고,
   이후에 더 꽂아야 한다면, 가장 늦게 필요한 것을 빼기로 했다.

문제 풀이

#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

map<int, vector<int>> usePos;   // 플러그별로 꽂아야하는 순서를 저장
map<int, int> nowPos;           // 플러그별로 현재 몇번째 순서인지를 저장
vector<int> order;              // 총 순서를 저장
set<int> multiTap;              // 멀티탭에 뭐가 꽂혀있는지 저장
int N, K, answer = 0;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;
    order = vector<int>(K);
    for (int i = 0; i < K; ++i)
    {
        cin >> order[i];
        usePos[order[i]].push_back(i);
    }

    for (int i = 0; i < K; ++i)
    {
        if (multiTap.find(order[i]) != multiTap.end())
        {
            nowPos[order[i]]++;
        }
        else
        {
            if (multiTap.size() == N)
            {
                // 하나를 뽑아야 하는 상황
                answer++;
                // 무엇을 뽑을것인가?

                int outNum = -1, outPos;
                for (int iter : multiTap)
                {
                    if (usePos[iter].size() == nowPos[iter])
                    {
                        outNum = iter;
                        break;
                    }
                    else
                    {
                        if (outNum == -1)
                        {
                            outNum = iter;
                            outPos = usePos[iter][nowPos[iter]];
                        }
                        else
                        {
                            if (outPos < usePos[iter][nowPos[iter]])
                            {
                                outNum = iter;
                                outPos = usePos[iter][nowPos[iter]];
                            }
                        }
                    }
                }
                multiTap.erase(outNum);
            }
            multiTap.insert(order[i]);
            nowPos[order[i]]++;
        }
    }

    cout << answer << '\n';

    return 0;
}

다시 생각해 볼 점

1. 그리디는 매 순간마다 ‘가장 ~한’을 찾는게 중요하다.
2. 우선순위 큐를 사용해보려고 했지만 이번엔 매번 큐 안의 내용이 바뀌어야해서 불가
3. 어차피 최대 100개이고 총 100회이기 때문에 1만번은 그냥 순회하면서 비교해도 가능하다고 생각했다.
4. 약간의 오류는 있을 줄 알았는데, 한번에 풀어서 기분이 좋다.