[알고리즘 문제] 20136번 멀티탭 스케줄링2

1. 문제설명

N개의 멀티탭 구멍이 존재하며 M번 전자기기를 사용한다. 이 때 멀티탭에서 전자기기를 빼야하는 최소 횟수는 몇 번인지 구해라. ( N , M <= 100,000)

20136번: 멀티탭 스케줄링 2

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

 

2. 접근 과정

1) 해석

주어진 순서대로 전자제품을 사용하고 이미 멀티탭이 꽉 차있을 경우 꽃혀있는 것 중 하나를 뽑아서 쓰면 된다. 이 때 무엇을 뽑을지 고민하면 되는데, 단순히 해당 전자제품이 그 후로 쓰이는 시간이 가장 큰 것을 뽑아서 쓰면 된다. 이는 멀티탭 스케줄링 1과 비슷한 해석이며 단순히 시간을 줄이기 위해 N번 도는 것이 아닌 logN번 돌게끔 코딩하면 된다.

 

2) 실패

struct Data
{
    int n;
    bool operator<(const Data&r) const{
        return chk[n] < chk[r.n];
    }
};

queue<int> v[500005], cmd;
priority_queue< Data > pq;

int main()
{
    pq.push(Data{0});
    while(!cmd.empty()){
        int n = cmd.front(), last = 21e8;
        cmd.pop(); v[n].pop();
        if(!v[n].empty()) last = v[n].front();
        int s = pq.size(), num = pq.top().n;
        if(!chk[n] && pq.size() > N){ ans++; pq.pop(); chk[num] = 0;}
        if(!chk[n]) pq.push(Data{n});
        chk[n] = last;
    }
}

 

처음 생각한 아이디어를 구현한 코드 중 일부이다. 이미 플러그에 해당 전자제품이 꽃혀 있을 경우 그 전자제품을 업데이트하면 되지 않을까? 하여 위와 같이 코드를 작성하였고 멀티탭에 꽃혀있는 전자제품 수를 pq.size() 를 통해 알아낼 수 있지 않을까 생각하여 위 처럼 코드를 짜개 되었다.

 

하지만 위 코드의 치명적인 실수가 있다. 그것은 바로 중간에 chk[n]을 바꿔도 priority_queue가 업데이트 되지 않는다는 점이었다. 이 사실을 관과하고 코드를 짰기에 이는 오답 코드가 된다.

 

3) 정답 + 코드

아이디어는 같으나 이미 존재하는 전자제품의 처리 부분을 어떻게 구현하면 좋을지 고민하다가 어차피 priority_queue와 입력 특성 상 이미 지난 것은 어차피 후순위로 밀려 무시되는 존재가 된다. 이 사실을 통해 이미 존재하는 플러그의 정보를 수정하지 말고 그냥 그 다음 정보를 입력해주면 된다. 그리고 멀티탭에 꽃힌 전자제품의 수를 pq.size()가 아니라 따로 카운트해주면 되는 문제였다. 

 

#include <bits/stdc++.h>
using namespace std;

int N, M, cnt, ans, chk[500005];
priority_queue< pair<int,int> > pq;
queue<int> cmd[500005], input;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    int x, er;
    for(int i=1; i<=M; i++){
        cin >> x;
        cmd[x].push(i);
        input.push(x);
    }
    
    while(!input.empty()){
        int n = input.front(), next = 21e8;
        input.pop(); cmd[n].pop();
        if(!cmd[n].empty()) next = cmd[n].front();

        if(cnt < N){
            if(chk[n]) cnt--;
            cnt++;
        }
        else{
            if(!chk[n]){
            er = pq.top().second, chk[er] = 0,ans++;
            pq.pop();
            }
        }
        chk[n] = next;
        pq.push(make_pair(next, n));
    }
    cout << ans;
}

 

3. 소감 및 교훈

여태까지 자료 구조 안의 데이터는 모두 사용되고 상황을 100% 설명 가능하게 사용한다고 생각하여 이미 존재하는 플러그의 경우 '수정해야 한다' 라고 생각하였고 플러그가 꽃힌 개수 또한 pq.size()로 고려해야 한다고 생각했다. 하지만 이 문제를 통해 자료 구조는 단순히 '수단'이고 그 상황을 100% 로 설명하지 않아도 된다는 사실을 뼈저리게 느끼게 되었다... 기존에는 너무 딱딱하게 자료구조를 사용하고 있었던 것 같다.