[프로그래머스] 택배상자 C++ 풀이 및 해설

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

프로그래머스

풀이 방법

내가 박스를 최대로 담을 방법은

메인 벨트에서 꺼낼 수 있다면 꺼내고

서브 벨트에서 꺼낼 수 있다면 꺼내고

메인도 서브도 안된다면 메인것을 서브로 옮겨보고 꺼낼 수 있는지 확인하고

그래도 안된다면 방법이 없는것이다.

 

순서대로 아래의 로직을 작성했다.

1. 메인 벨트에서 꺼낼 수 있나?

2. 서브벨트에서 꺼낼 수 있나?

3. 메인벨트에서 서브벨트로 옮길 상자가 있다면 옮겨보자

4. 다 안된다면 방법이없어~

 

헷갈린 부분이 서브 벨트의 상자를 메인 벨트로 옮길 수 있을까였다.

컨테이너 벨트는 한 방향으로만 진행이 가능

즉, 뒤로 갈 수 없다. 그러니 못 옮긴다고 가정하고 풀었다.

 

 

추가적인 상세한 풀이 방법은 주석으로 달아놓았다.

전체 코드

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

int solution(vector<int> order) {
    int answer = 0;
    stack<int> subBelt;
    
    int mainBelt=1; // 현재 메인 벨트의 맨 앞 상자 번호
    while(1) {
        // order[answer]는 헌재 내가 꺼내야하는 박스 번호이다.
        if(order[answer]==mainBelt) { // 꺼내야하는 상자와 메인벨트 상자가 일치하면
            mainBelt++;
            answer++;
        } else if(!subBelt.empty() && order[answer]==subBelt.top()) {// 꺼내야하는 상자와 서브벨트 상자와 일치하면
            subBelt.pop();
            answer++;
        } else if(mainBelt+1<=order.size()) { // 메인벨트에서 서브벨트로 옮길 상자가 있다면
            subBelt.push(mainBelt);
            mainBelt++;
        } else { // 모두 해당하지 않으면 메인벨트도 서브벨트에서 해결할 수 없는 상황임
            break;
        }
        
    }
    
    return answer;
}