[programmers] 택배상자

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

queue와 stack

 

---------------------------------------------------풀이----------------------------------------------------

 

컨테이너벨트는 1부터 N까지 순서대로 출력되는 queue라고 볼 수 있다.

보조컨테이너벨트는 LIFO 구조의 stack이다.

각 순서에 맞게 트럭에 싣는 것이 목표이므로, order 순서대로 다음 작업을 반복한다.

먼저, stack top에 원하는 번호가 존재하면 pop하고(트럭에 싣고) 다음 순서로 넘어간다.

stack top에 원하는 번호가 없는 경우, queue에도 없는지 체크한다.

현재 컨테이너벨트의 맨 앞 숫자 q가 order[i]보다 작거나 같아야 보조컨테이너벨트로 옮겨 실어서 order[i]를 꺼낼 수 있다.

따라서 q가 order[i]보다 크면 어떤 컨테이너벨트에서도 구할 수 없는 것이므로 종료한다.

q <= order[i]인 경우, q가 order[i]와 같아질 때까지 stack에 q를 넣으면서 증가시킨다.

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

using namespace std;

// 1~n번 순서대로 전달됨.
// 택배 기사님이 미리 알려준 순서에 맞게 택배상자를 실어야 함.
// 컨테이너벨트(큐)-보조컨테이너벨트(스택)-트럭
// 원하는 순서대로 실을 수 없으면 종료.
int solution(vector<int> order) {
    int answer = 0;
    int q = 1;  // 현재 컨테이너 벨트에서 꺼낼 수 있는 숫자
    stack<int> s;
    for(int i = 0; i < order.size(); i++){
        // 보조 컨테이너 벨트에 원하는 번호가 있는 경우
        if(!s.empty() && s.top() == order[i]){
            s.pop();
            answer++;
            continue;
        }
        // 컨테이너 벨트에서도 꺼낼 수 없는 경우 종료
        if(q > order[i]){
            break;
        }
        // 컨테이너 벨트에 원하는 번호가 있는 경우
        while(q < order[i]){
            s.push(q);
            q++;
        }
        q++;
        answer++;
    }
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

매우 간단한 stack 활용 문제.