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

프로그래머스

영재는 택배상자를 트럭에 싣는 일을 합니다. 1번 상자부터 N번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 실을 수 있고

앞뒤로 움직이는 보조 컨테이너 벨트에 임시로 상자를 실을 수도 있습니다. 택배 기사님이 원하는 상자 순서대로 메인 컨테이너 벨트에 상자를 보낼 때, 총 몇개를 보낼 수 있는지 구해주세요.

[4, 3, 1, 2, 5]를 입력 받을 때, 첫번 째로 4를 보내기 위해서 보조 벨트에 1, 2, 3을 보내고 메인 벨트에 4를 보냄, 이후 보조 벨트에 3을 꺼내서 보내고 마무리. 총 2개

 

풀이 방법

1. 초기 변수 선언

• stack<int> s: 스택은 임시로 상품을 보관하는 공간을 표현합니다.
• int cur = 1: 현재 벨트에서 나오는 상품 번호를 추적합니다. 벨트의 첫 번째 상품은 항상 1부터 시작합니다.
• int answer = 0: 올바른 순서로 정리된 상품의 개수를 기록합니다.

stack<int> s;
int cur = 1;
int answer = 0;

 

2. 반복문: 주어진 order 배열을 순회

• for (int n : order): order 배열의 각 요소 n에 대해 반복하며, 이를 순서대로 처리합니다.

for (int n : order)
{
    if (n >= cur)
    {
        while (n > cur)
            s.push(cur++);        
        cur++;
    }

    else if (s.top() == n)
        s.pop();

    else
        break;

    answer++; 
}

 

• n >= cur인 경우 (벨트에서 상품 꺼내기):
  • n이 현재 벨트에서 나오는 상품 번호 cur보다 크거나 같으면, cur부터 n까지 스택에 넣습니다.
  • while (n > cur):
    • cur을 스택에 추가하며, cur++를 통해 다음 상품으로 이동합니다.
  • 마지막으로, cur이 n일 때, 스택에 추가하지 않고 바로 다음 상품으로 넘어갑니다 (cur++).
• n < cur인 경우 (스택에서 상품 꺼내기):
  • 이 경우, 스택의 맨 위 요소(s.top())가 n인지 확인합니다.
  • if (s.top() == n):
    • 스택의 맨 위 상품이 정리할 상품 번호와 같다면, 스택에서 꺼냅니다 (s.pop()).
• 위 조건을 만족하지 못하는 경우:
  • 만약 n이 현재 벨트에서 꺼낼 수도 없고, 스택에서도 꺼낼 수 없다면 정리를 중단합니다.

 

정답 코드

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

using namespace std;

int solution(vector<int> order) {
    
    stack<int> s;
    int cur = 1;
    int answer = 0;
    
    for (int n : order)
    {
        if (n >= cur)
        {
            while (n > cur)
                s.push(cur++);        
            cur++;
        }
        
        else if (s.top() == n)
            s.pop();
        
        else
            break;
        
        answer++; 
    }
    
    return answer; 
}