[ 프로그래머스 ] 택배상자

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/131704

풀이

---

원하는 순서로 배열의 배치를 바꾸는 문제로, 배치를 바꾸기 위해 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있는 보조 컨테이너 벨트, 즉 stack을 활용한 문제이다.

#include <string>
#include <vector>
#include <stack>

using namespace std;

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

    // 1 ~ n 까지 순서대로 전달, 순서대로 내림
    // 맨앞의 상자가 싣려야할 상자가 아닐시 보관, 보관하는데는 가장 마지막에 보관하는거 순서
    // 원하는 순서로 실리지 않는다면 더이상 실지 않는다.

    vector<int> final_rail;
    stack<int> assist_rail;

    int num_box = 1;
    int idx = 0;

    while(num_box < order.size() + 2)
    {
        if (!assist_rail.empty() && assist_rail.top() == order[idx])
        {
            final_rail.push_back(assist_rail.top());
            assist_rail.pop();
            idx++;
        }

        else if (idx < order.size() && order[idx] == num_box)
        {
            final_rail.push_back(order[idx]);
            num_box++;
            idx++;
        }

        else
        {
            assist_rail.push(num_box);
            num_box++;
        }
    }

    answer = final_rail.size();

    return answer;
}