[코드트리] 산타 선물 공장2(deque, priority_queue) - 시간초과

https://www.codetree.ai/training-field/frequent-problems/problems/santa-gift-factory-2/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

작년 삼성 시험 때 테스트케이스 한개 오류 난 문제

그 때와 다르게 deque, priority_queue를 사용해 봤는데 TestCase는 모두 맞지만 시간초과 난다.

---

---

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <functional>
#include <cmath>
#include <ctime>

using namespace std;


vector<deque<int>>
installFactory(int n, int m, vector<int> &v)
{
    vector<deque<int>> belt(n);
    //vector<priority_queue<int, vector<int>, less<int>>> tmpBelt(n);
    vector<priority_queue<int, vector<int>, greater<int>>> tmpBelt(n);
    //priority_queue<int, vector<int>, greater<int>> q1;

    for (int i = 0; i < m; i++)
    {
        (tmpBelt[v[i] - 1]).push(i + 1);
    }
    
    for (int i = 0; i < n; i++)
    {
        int size = tmpBelt[i].size();
        for (int j = 0; j < size; j++) {
            belt[i].push_back((tmpBelt[i]).top());
            tmpBelt[i].pop();
        }
    }

    return belt;
}

void
moveAll(int src, int dst, vector<deque<int>> &belt)
{
    if (!belt[src - 1].empty())
    {
        int qsize = belt[src - 1].size();
        for (int i = 0; i < qsize; i++)
        {
            belt[dst - 1].push_front(belt[src - 1].back());
            belt[src - 1].pop_back();
        }
    }
}

void
changeFront(int src, int dst, vector<deque<int>> &belt)
{
    int srcFr = 0, dstFr = 0;
    if (!belt[src - 1].empty()) {
        srcFr = belt[src - 1].front();
        belt[src - 1].pop_front();
    }
    if (!belt[dst - 1].empty())
    {
        dstFr = belt[dst - 1].front();
        belt[dst - 1].pop_front();
    }

    if (srcFr) belt[dst - 1].push_front(srcFr);
    if (dstFr) belt[src - 1].push_front(dstFr);

}

void
shareGift(int src, int dst, vector<deque<int>> &belt)
{
    int mvCnt = floor(belt[src - 1].size() / 2);
    deque<int> tmp;
    while (mvCnt--)
    {
        tmp.push_back(belt[src - 1].front());
        belt[src - 1].pop_front();
    }
    int qSize = tmp.size();
    while (qSize--)
    {
        belt[dst - 1].push_front(tmp.front());
        tmp.pop_front();
    }

}

int
getGiftInfo(int num, vector<deque<int>> belt)
{
    int a = -1, b = -1;
    for (int i = 0; i < belt.size(); i++)
    {
        int qsize = belt[i].size();
        for (int j = 0; j < qsize; j++)
        {
            if (belt[i][j] == num)
            {
                if (j == 0) a = -1;
                else a = belt[i][j - 1];

                if (j == qsize - 1) b = -1;
                else b = belt[i][j + 1];
            }
            else continue;
        }
    }

    return (a + 2 * b);
}

int getBeltInfo(int num, vector<deque<int>> belt)
{
    int a = -1, b = -1, c = 0;

    if (!belt[num - 1].empty())
    {
        a = belt[num - 1].front();
        b = belt[num - 1].back();
        c = belt[num - 1].size();
    }

    return (a + 2 * b + 3* c);
}


int main() {

    clock_t start, finish;
    double duration;

    start = clock();

    int q;
    vector<deque<int>> belt;
    cin >> q;

    vector<int> command(q, 0);
    for (int i = 0; i < q; i++)
    {
        cin >> command[i];
        switch (command[i])
        {
        case 100 :
		{
            int n, m;
            cin >> n >> m;
            vector<int> b(m, 0);
            for (int i = 0; i < m; i++)
            {
                cin >> b[i];
            }
            belt = installFactory(n, m, b);
			break;
		}
        case 200 :
        {
            int m_src, m_dst;
            cin >> m_src >> m_dst;
            moveAll(m_src, m_dst, belt);
            cout << belt[m_dst - 1].size() << endl;

            break;
        }
        case 300:
        {
            int m_src, m_dst;
            cin >> m_src >> m_dst;
            changeFront(m_src, m_dst, belt);
            cout << belt[m_dst - 1].size() << endl;

            break;
        }
        case 400:
        {
            int m_src, m_dst;
            cin >> m_src >> m_dst;
            shareGift(m_src, m_dst, belt);
            cout << belt[m_dst - 1].size() << endl;
            break;
        }
        case 500: 
        {
            int p_num;
            cin >> p_num;
            cout << getGiftInfo(p_num, belt) << endl;
            break;
        }
        case 600:
        {
            int b_num;
            cin >> b_num;
            cout << getBeltInfo(b_num, belt) << endl;
            break;
            break;
        }
        }
    }

    finish = clock();

    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << duration << "초" << endl;

    return 0;
}