백준 1700번 - 멀티탭 스케줄링 (C++)

문제

해결 방법

그리디 알고리즘을 사용하며 현재 멀티탭에 꽂혀 있는 용품 중, 이후에 등장하지 않는것을 뽑고, 이후에 등장하지 않는 용품이 없다면 그중 가장 나중에 사용하는 것 순서로 제거하면 된다. 이를 위하여 입력 시, 벡터에 용품들이 사용되는 순서에 대하여 2차원 배열 형태로 추가로 저장하였다.

아쉬웠던 점

골드 1이라 기대했는데 너무 쉬웠다. 특히 문제의 범위가 너무 좁아 삭제가 들어간 내 코드도 0ms가 나와서 상위권의 좋은 코드들을 보지 못하는 것도 단점이라고 생각한다.

코드

#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int Num, Using_Num, Ans = 0;
    cin >> Num >> Using_Num;
    set<int> Tap; //멀티탭
    vector<int> Using_Vec(Using_Num); //전기용품 사용 순서
    vector<vector<int>> Using_Timing(101); //해당 용품이 언제 사용되는지 모두 저장.
    for (int i = 0; i < Using_Num; ++i)
    {
        cin >> Using_Vec[i];
        Using_Timing[Using_Vec[i]].emplace_back(i);
    }
 
    for (int i = 0; i < Using_Num; ++i)
    {
        //멀티탭 꽉 차고, 넣으려는 숫자가 탭에 없을 때 = 하나 뽑고 넣어야 할 때.
        if (Tap.size() == Num && Tap.count(Using_Vec[i]) == 0) 
        {
            int a = 0, b = 0;
            for (set<int>::iterator iter = Tap.begin(); iter != Tap.end(); iter++)
            {
                //앞으로 안나오는거 우선 제거.
                if (Using_Timing[*iter].empty())
                {
                    b = *iter;
                    break;
                }
                //이후에 늦게 나오는거 대상으로 지정.
                else if (Using_Timing[*iter].front() > i)
                {
                    if (a < Using_Timing[*iter].front())
                    {
                        a = Using_Timing[*iter].front();
                        b = *iter;
                    }
                }
            }
            
            //대상 삭제
            Tap.erase(Tap.find(b));
            Ans++;
        }
 
        //멀티탭에 현재 사용 용품 추가. set사용하여서 중복일 경우 무시됨.
        Tap.insert(Using_Vec[i]);
        //용품 사용 기록에서 현재 사용을 제거.
        Using_Timing[Using_Vec[i]].erase(Using_Timing[Using_Vec[i]].begin());
    }
    cout << Ans;
}

삭제를 사용하지 않고 해결하려면 매번 뒤에서부터 현재 위치까지 순회하며 가장 순서가 나중인것/혹은 나오지 않는것을 찾아 대상을 삭제 해야할 것 같은데 그보다는 쿨하게 삭제하며 진행하는게 더 깔끔할 것 같았다.

 

잡설 : 잠이 안와서 간만에 주석좀 이쁘게 달았다 ㅋㅋ 그리고 이게 어떻게 골드 1이지....????