C++ / 프로그래머스 / 택배상자

문제

 

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

프로그래머스

 

문제풀이

 

경우의 수를 따져가며 풀어야 되는 문제인지 알고 조건을 여러 개 두어 풀었는데..

다른 풀이를 보니 스택에 다 집어넣고 pop 하면서 푸는 풀이가 있더라고요..

저는 제가 푼대로 풀이하겠습니다.

 

컨베이어 벨트의 맨 앞에 있는 박스를 box_num이라는 변수의 값으로 둔다.

보조 컨테이어 벨트를 나타내는 박스들을 stack을 이용해 표기한다.

(스택의 top부분이 보조 컨베이어 벨트에서 꺼낼 수 있는 상자)

현재 트럭에 실어야 하는 박스를 need라는 변수의 값으로 둔다.

 

    while (1) {
        if (order_idx >= N) break;
        need = order[order_idx];
        if (box_num > N && !stk.empty() && stk.top() != need) break;

 

 

만약 트럭에 모든 상자를 실었다면 반복문을 종료한다.

현재 실어야 하는 박스는 order의 order_idx번째에 있는 상자이다.

만약 컨베이어 벨트에서 모든 상자를 트럭에 싣든, 보조 컨테이어 벨트에 실어, 더 이상 꺼낼 박스가 없고, 보조 컨테이어의 맨 앞 박스가 필요한 박스가 아니라면 반복문을 종료한다.

 

        if (need == box_num) {
            ++order_idx;
            ++box_num;
            ++answer;
        }
        else if (!stk.empty() && stk.top() == need) {
            ++order_idx;
            ++answer;
            stk.pop();
        }
        else {
            stk.push(box_num++);
        }

컨베이어 벨트의 맨 앞 박스가 필요한 박스라면 order_idx, box_num, answer에 1씩 더해준다.

 

그렇지 않다면 보조 컨테이어를 살펴 맨 앞 박스가 필요한 박스라면 order_idx, answer에 1씩 더해준다. 그리고 pop을 한다. 이 때는 컨베이어벨트에서 박스를 꺼낸 것이 아니므로 box_num은 그대로 유지한다.

 

그 외의 경우는 보조 컨베이어 벨트에 넣는다. (stk.push)

이를 반복문이 종료될 때까지 반복한다.

 

반복문이 종료되면 더 이상 작업을 수행할 수 없는 상태이므로 answer을 return 한다.

 

 

코드

#include <string>
#include <vector>
#include <stack>
using namespace std;

int solution(vector<int> order) {
    int N = order.size();
    int order_idx(0), answer(0), need(0);
    stack<int>stk;

    int box_num = 1;
    while (1) {
        if (order_idx >= N) break;
        need = order[order_idx];
        if (box_num > N && !stk.empty() && stk.top() != need) break;
        if (need == box_num) {
            ++order_idx;
            ++box_num;
            ++answer;
        }
        else if (!stk.empty() && stk.top() == need) {
            ++order_idx;
            ++answer;
            stk.pop();
        }
        else {
            stk.push(box_num++);
        }
    }

    return answer;
}