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

택배상자

문제 링크

택배상자

분석

컨베이어 벨트에 상자를 트럭에 실어야 합니다.
원하는 순서에 맞는 경우 트럭에 실을 수 있습니다.
원하는 순서에 맞지 않은 경우 보조 컨테이너 벨트에 넣어둘 수 있습니다.
보조 컨테이너 벨트에 있는 상자가 원하는 순서에 맞는 상자인 경우 보조 컨테이너 벨트에서 트럭으로 실을 수 있습니다.
만약 원하는 순서의 상자를 넣을 수 없는 경우 더 이상 싣지 않습니다.
트럭에 실을 수 있는 총 상자의 개수를 반환하면 됩니다.

보조 컨테이너 벨트는 앞 뒤로 이동이 가능하며, 입구 외에 다른 면이 막혀있는 구조(후입선출)이므로, 스택을 사용하면 됩니다.

풀이

#include <vector>
#include <stack>

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    
    stack<int> subContainerVelt;    // 보조 컨테이너 벨트
    int index = 0;  // 트럭에 실어야 하는 상자의 순서
    int currentBox = 1; // 원하는 상자의 순서
    
    // order를 기준으로 배열 반복
    while (index < order.size())
    {
        // 보조 컨테이너 벨트가 비어있지 않고, 보조 컨테이너에서 상자를 실을 수 있는지 확인
        if (!subContainerVelt.empty() && subContainerVelt.top() == order[index])
        {
            subContainerVelt.pop();
            ++index;
            ++answer;
        }
        // 컨테이너 벨트에서 가져올 상자가 있는지 확인
        else if (currentBox <= order.size())
        {
            // 원하는 순서와 현재 넣어야 하는 상자의 순서가 같은 경우
            if (currentBox == order[index])
            {
                ++index;
                ++answer;
            }
            else
            {
                // 보조 컨테이너 벨트에 임시 보관
                subContainerVelt.push(currentBox);
            }
            
            ++currentBox;
        }
        // 컨테이너 벨트에서 가져올 수 있는 상자가 없고, 넣을 수 있는 상자가 없는 경우 반복문 종료
        else
        {
            break;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(N)$입니다.

• order를 순회하는 반복문 $O(N)$

공간 복잡도는 $O(N)$입니다.

• 보조 컨테이너 벨트 stack<int> subContainerVelt $O(N)$

테스트 1 〉 통과 (1.43ms, 7.56MB)
테스트 2 〉 통과 (5.47ms, 23.1MB)
테스트 3 〉 통과 (4.91ms, 29.2MB)
테스트 4 〉 통과 (5.18ms, 21.5MB)
테스트 5 〉 통과 (7.52ms, 42.4MB)
테스트 6 〉 통과 (2.19ms, 10.7MB)
테스트 7 〉 통과 (8.82ms, 33.1MB)
테스트 8 〉 통과 (0.50ms, 4.82MB)
테스트 9 〉 통과 (7.88ms, 23.8MB)
테스트 10 〉 통과 (10.16ms, 38.5MB)