[Lv 2] 택배상자

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

프로그래머스

 

컨테이너 벨트는 순차적으로 흘러가며, 임시 컨테이너 벨트는 stack의 형태로 이루어져 있다.

order 배열에 값은 택배 기사가 임의로 정하며

컨테이너 벨트와 임시 컨테이너 벨트에서 order의 형태로 값을 뽑지 못한다면 택배 상자를 옮기지 않는다.

 

따라서 임시 컨테이너는 stack이나 vector를 사용해 구현한다.

또한, 컨테이너는 순차적으로 흘러가므로 for문을 사용해 구현했다.

i값이 order[idx]에 해당하는 경우는 컨테이너 벨트의 값이 order에 해당하는 경우이다.

이때, answer의 수와 order의 idx를 증가시킨다.

 

만약 다르다면 임시 컨테이너에 컨테이너의 값을 삽입한다.

이후, 임시 컨테이너의 top 값이 order[idx]에 해당하면 

answer의 수와 order의 idx를 증가시킨다. 또한, 임시 컨테이너의 top을 제거한다.

위 과정은 임시 컨테이너가 비거나, top이 order[idx]가 일치하지 않을 때 까지 반복한다.

 

만약, 임시 컨테이너 top 값과 현재 컨테이너의 값이 order[idx]와 일치하지 않는다면

계속해서 컨테이너는 흘러갈 것이다.

그러면 answer는 증가하지 않으므로 택배 상자를 싣지 않을 것이다.

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    
    // 보조 컨테니어는 가장 마지막에 보관한 상자만 뺄 수 있음
    vector<int> tempContainer;
    int idx = 0;
    
    // 컨테이너 벨트는 순차적으로 전달
    for(int i = 1;i<=order.size();i++){
        if(i == order[idx]){
            answer++;
            idx++;
        }
        // 맨앞 상자가 실어야하는 순서가 아니면 잠시 다른곳(보조 컨테이너)에 보관
        else{
            tempContainer.push_back(i);
        }
        // 보조 컨테이너를 사용해도 원하는 순서대로 싣지 못하면 상자를 싣지 않음
        while(!tempContainer.empty()){
            if(tempContainer.back() != order[idx])
                break;
            
            answer++;
            idx++;
            tempContainer.pop_back();
        }
    }
   
    return answer;
}