택배 상자 / stack

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

문제를 요약하자면, 1~n까지 순서대로 메인 컨테이너 벨트에서 상자가 나오는데 이것을 order 순서에 맞게 트럭에 실어야한다.
보조 컨테이너 벨트가 존재하는데, 메인 컨테이너에서 나오는 상자와 order 순서가 맞지 않을 경우 보조 컨테이너에 순차적으로 넣어 보관이 가능하다. 이 보조 컨테이너는 stack처럼 후입선출 구조이다.

메인 컨테이너 벨트와 보조 컨테이너 벨트 모두 사용해서 order 순서에 맞게 몇 개의 상자를 실을 수 있는지 묻는 문제이다.

 

✅ 보조 컨테이너 stack을 사용한 풀이

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

using namespace std;

void check_temp(const vector<int>& order, stack<int>& temp_container, int& idx, int& box_cnt)
{
    while (!temp_container.empty() && order[idx] == temp_container.top())
    {
        temp_container.pop();
        idx++;
        box_cnt++;
    }
}

int solution(vector<int> order)
{
    stack<int> temp_container;
    int idx = 0;
    int box_cnt = 0;

    for (int i = 1; i <= order.size(); ++i)
    {
        // i가 order와 같다면
        if (i == order[idx])
        {
            idx++;
            box_cnt++;
            // 보조 컨테이너에서 order 처리
            check_temp(order, temp_container, idx, box_cnt);
        }
        // i가 order와 다르다면
        else
        {
            // 보조 컨테이너에 i 저장
            temp_container.push(i);
            // 보조 컨테이너에서 order 처리
            check_temp(order, temp_container, idx, box_cnt);
        }
    }

    return box_cnt;
}

order와 현재 메인 컨테이너 벨트에서 나오는 상자가 일치한다면, 바로 box_cnt를 증가시켜주고 order의 인덱스를 증가 시켜준다. 그리고 만약 order와 다른 상자가 나온다면 보조 컨테이너인 stack<int> temp_container에 저장시켜준다.

두 상황 모두 check_temp 매서드를 호출하는데, 루프를 돌며 order 순서와 보조컨테이너 순서가 같다면 box_cnt를 증가시켜주었다.

 

✅ 타인 풀이

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

using namespace std;

int solution(vector<int> order) 
{
    int answer = 0;
    stack<int> st;
    for (int i = 1; i <= order.size(); ++i)
    {
        st.push(i);

        while (!st.empty() && order[answer] == st.top())
        {
            st.pop();
            answer++;
        }
    }
    return answer;
}

똑같이 Stack을 사용해서 푼 사람인데, 애초에 컨테이너 벨트를 stack 하나로만 두고 1~order size를 넣을 때마다 while문으로 바로바로 체크해서 answer의 값을 증가시켜주었다.
그리고 어차피 answer의 값이 order의 순서이므로 따로 변수를 두지 않아서 훨씬 코드가 심플하고 불필요한 함수와 변수가 제거된 느낌이었다.

나의 코드에선 문제 지문의 흐름에 따라 코드를 작성하다보니 뭔가 불필요한 살이 붙어있는 느낌인데, 이 분의 코드를 보았을 때 문제의 요지를 정확하게 판단해서 불필요한 코드가 없다는 느낌이 들었다.