택배상자(50분)

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

구현 아이디어 3분 구현 47분

풀이

무난하게 접근했다가 시간 싸움에 처참히 패배한 문제. 잡아야 할 조건이 많았다.

1. order의 길이만큼 queue에 택배상자를 넣는다.
2. 스택이 비어있지 않다면 현재 택배상자와 top이 같은지 확인한다.

• for문을 돌 때 i를 무조건 증가하면 안된다. 조건에 따라 i를 조절해 줘야 한다.

3. 같지 않다면 큐에서 해당 택배상자가 있는지 확인한다.
4. for문이 끝난 뒤에 스택을 한번 더 확인한다.
5. answer는 스택에 남아있는 택배상자의 개수를 뺀 값이다.

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

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    int N = order.size();
    
    queue<int> main;
    stack<int> sub;
    
    for(int i = 0; i < N; ++i) main.push(i + 1);
    
    int i = 0;
    bool find_sub = false;
    for(; i < N; ++i)
    {
        int cur_box = 0;
        find_sub = false;
        
        while(!sub.empty() && i < N)
        {
            cur_box = order[i];
                
            int pick_box = sub.top();
            if(pick_box == cur_box)
            {
                ++i;
                sub.pop();
                find_sub = true;
            }
            else
            {
                find_sub = false;
                break;
            };
        }
        if(!find_sub && main.empty()) break;
        if(!main.empty() && i < N)
        {
            cur_box = order[i];
            
            int pick_box = main.front();
            if(pick_box == cur_box)  main.pop();
            else 
            {
                main.pop();
                sub.push(pick_box);
                --i;
            }
        }
    }
    
    for(int i = N - sub.size(); i < N; ++i)
    {
        if(sub.top() == order[i]) sub.pop();
        else break;
    }
    
    return answer = N - (sub.size());
}