[백준/C++] 1700번 멀티탭 스케줄링

---

컴퓨터 구조 시간에 Memory Replacement Algorithm에 대해 배운 적이 있는데 그 때 LRU 등등 다양한 알고리즘을 배우다가

뒤에 올 것이 무엇인지 알면 가장 직후에 사용될 것을 찾는 방법이 optimal한 방법이라고 하였다.

그 때는 뒤에 어떤 것이 올지 알 수 없었지만 문제에서는 알 수 있으니 greedy하게 풀어낼 수 있을 것이라고 생각했는데 가지고 있는 것들 중에 더 일찍 재사용될 친구를 찾는다는게 생각보다 어려워서 숫자도 100으로 크지 않으니 queue를 각 아이템마다 만들어서 풀어내려고 하였다.

들어오는 순서대로 queue에 넣고 다음에 오는 숫자가 가장 느린 친구를 pop시켜주고 이미 가지고 있다면 continue 하는 방식으로 코드를 구현하였다.

 

코드를 구현할 때 이미 코드를 꽂은 아이템을 콘센트가 비어있을 때 계속 넣는 실수를 했었다.. ㅎ

---

#include <bits/stdc++.h>
using namespace std ;
int hole, item, temp, answer ;

int main()
{
    cin >> hole >> item ;
    int arr[item+1] ;
    queue<int> que[item+1] ;
    vector<int> lotate ;

    for(int i = 0 ; i < item ; i++)
    {
        cin >> temp ;
        arr[i] = temp ;
        que[temp].push(i) ;
    }

    for(int i = 0 ; i < item ; i++)
    {
    	//콘센트 자리가 남을 경우
        if(lotate.size() < hole)
        {
            bool flag = 1 ;
            for(int it : lotate)
            {
            	// 이미 코드를 꼽은 물건일 경우
                if(it == arr[i])
                {
                    flag = 0 ; break ;
                }
            }
            if(flag) lotate.push_back(arr[i]) ;
        }
        else 
        {
            bool flag = 0 ;
            int out = 0 ;
            //콘센트 내에서 가장 늦게 재사용할 물건을 찾음
            for(int j = 0 ; j < lotate.size() ; j++)
            {
                int now = lotate[j] ;
                if(now == arr[i])
                {
                    flag = 1 ; break ;
                }
                else
                {
                    if(que[lotate[out]].empty()) continue ;
                    if(que[now].empty() || que[now].front() > que[lotate[out]].front())
                        out = j ;
                }
            }

            if(!flag)
            {
                answer++ ;
                lotate[out] = arr[i] ;
            }
        }

        que[arr[i]].pop() ;
    }

    cout << answer ;
}

---

느낀점: 다른 사람들 코드를 보니 간결하다.. 또한 질문 게시판에 반례도 엄청 잘 되어 있어서 도움을 많이 받았는데 스스로 반례를 찾는 연습을 해야겠다...

 

문제링크: https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링