LV2.택배상자

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

프로그래머스

문제 내용 :

1.택배차가 원하는 택배번호 순서대로 택배를 실어야 함(인자값 : vector<int> order)

2.메인 컨테이너 벨트에 오름차순으로 택배가 존재하며,제일 앞에 택배만 꺼낼 수 있음

3.택배차에 짐을 실을때 원하는 택배가 아닌경우 서브 컨테이너 벨트에 택배를 보관할수 있음,

3-1.서브컨테이너 벨트는 제일 마지막에 쌓은 택배만 꺼낼 수 있음

4.두 벨트 에서 원하는 택배를 못 실을 경우 택배차는 출발함

이때 택배차에 몇개의 택배를 실을수 있는지 최대값을 찾는 문제 

---

풀이 : 

문제내용1 -> queue 자료구조에 적합 (순서대로 작업함에 따라 택배를 실고 삭제할때 앞에 원소 삭제하기가 용이함)

문제내용2 -> queue 자료구조에 적합

문제내용3 -> stack 자료구조에 적합

 

택배차의 queue<int> order를 순회하며 메인벨트(queue)와 서브벨트(stack)을 체크하며 answer의 값을 증가,

두 벨트에서 짐을 다 못 실을 경우 서브벨트에 택배를 쌓는다.

만약 메인벨트에서 더이상 서브벨트로 넣을 택배가 없으면  반복문에서 탈출하여 그대로 answer를 반환

---

코드 영역

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

using namespace std;

//1.메인벨트와  적재 박스 비교
//2.같은경우 벨트와 적재박스 큐에서 제외 후 ,answer증가
//3.다른경우 서브벨트 top과 비교해서 같은경우 stack과queue에서 제외후 answer증가
//3.둘다 다른경우 서브벨트에 적재

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

    queue<int> q_order; // 기사님이 원하는 택배 순서
    queue<int> main_belt;// 메인 컨테이너벨트
    stack<int> sub_belt; // 서브 컨테이너벨트
    
    //택배차의 원하는 택배순서를 queue로 저장
    for (int i = 0; i < order.size(); i++)
    {
        main_belt.push(i + 1); 
        q_order.push(order[i]); 
    }

    while (!q_order.empty())
    {
        //메인 벨트의 택배와 택배차의 order list와 비교
        if (!main_belt.empty() && q_order.front() == main_belt.front())
        {
            answer++;
            q_order.pop();
            main_belt.pop();
        }
        //서브 벨트의 택배와 택배차의 order list와 비교
        else if (!sub_belt.empty() && q_order.front() == sub_belt.top())
        {
            answer++;
            q_order.pop();
            sub_belt.pop();
        }
        //메인 벨트의 서브 벨트 둘다 택배가 없는경우
        else
        {
            //메인 벨트에 택배가 있으면 서브벨트에 해당 택배를 보관 후 다시 순회
            if (!main_belt.empty())
            {
                sub_belt.push(main_belt.front());
                main_belt.pop();
            }
            //메인 벨트에 택배가 없으면 더이상 할 수 없으므로 탈출후 반환
            else { return answer; }
        }

    }

    return answer;
}