[Programmers] Level2 : 택배 상자

Question

---

Solution

• 보조와 메인 벨트 역할을 할 stack sub, vector main을 선언한다. (main은 1번부터 나가야 하기 때문에 오름차순 정렬한다)
• 보조 벨트가 empty가 아니라면 가장 앞의 아이템과 타겟을 먼저 비교한다. 같으면 answer을 증가하고 해당 아이템을 뺀다.
• 메인 벨트가 empty가 아니라면 가장 앞의 아이템과 타겟을 비교한다. 다르다면 해당 아이템을 보조로 옮긴다.
• 위 두 조건에 해당되지 않으면 루프를 종료 시킨다.

---

Cord

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

bool myCompare(int a, int b)
{
    return a > b;
}

int solution(vector<int> order)
{
    int answer = 0;

    stack<int> sub;
    vector<int> main = order;
    sort(main.begin(), main.end(), myCompare);


    // target     //  main         // sub     // result
    // 4          (5 4 3 2 1)      ()
    //            (5 4 3 2)        (1)        1 -> sub
    //            (5 4 3)          (1 2)      2 -> sub
    //            (5 4)            (1 2 3)    3 -> sub
    //            (5)              (1 2 3)    4 -> truck  
    // 3          (5)              (1 2)      3 -> truck


    for (int target = 0; target < order.size(); ++target)
    {
        while(true)
        {
            // 보조 벨트의 첫 번째 택배 (항상 보조벨트먼저 확인하기)
            if (!sub.empty())
            {
                if (order[target] == sub.top())
                {
                    ++answer;
                    sub.pop();
                    break;
                }
            }

            // 메인 벨트의 첫 번째 택배
            if (!main.empty())
            {
                if (order[target] == main.back())
                {
                    ++answer;
                    main.pop_back();
                    break;
                }
                else
                {
                    sub.push(main.back());
                    main.pop_back();
                    continue;
                }
            }

            // 아무 조건에 만족 못하면 종료
            return answer;
        }
    }

    return answer;
}

---

Result