프로그래머스 - 택배상자 [C++]

 이 문제는 스택을 사용하는 문제이다. order의 최대 길이가 100만이므로 O(n) 시간 이하 알고리즘을 사용해야 한다. 문제를 잘 읽어보면 보조 컨베이어 벨트가 스택 구조라는 것을 알 수 있다. 처음에 알고리즘을 구상할 때는 box와 order를 한 루프 안에 전부 해결하려고 했으나, 이렇게 하면 로직이 매우 복잡해진다. 일단 box에 대해 모든 연산을 다 수행한 뒤, 스택에 남은 것을 처리하는게 훨씬 간편하게 구현할 수 있었다.

 

 

 한가지 주의할 점은 box 반복문에서 st.top()이 현재 order와 같은 경우 box를 고려하지 않았는데 for문에 의해 더해지므로 box--을 해놔야 box는 그대로고 스택에서만 뺄 수 있다는 것이다. 이 부분만 생각할 수 있다면 구현은 어렵지 않은 문제였다.

 

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

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    
    int orderIndex = 0;
    stack<int> st;
    
    for (int box = 1; box <= order.size(); box++) {
        if (box == order[orderIndex]) {
            answer++;
            orderIndex++;
        }
        else if (!st.empty() && st.top() == order[orderIndex]) {
            box--;
            answer++;
            st.pop();
            orderIndex++;
        }
        else {
            st.push(box);
        }
    }
    
    while (orderIndex < order.size()) {
        if (st.top() == order[orderIndex]) {
            answer++;
            orderIndex++;
            st.pop();
        }
        else {
            break;
        }
    }
    
    return answer;
}