프로그래머스 레벨2 <택배상자> C++ 풀이

두개의 컨테이너 벨트를 사용해서 주어진 order에 맞게 택배를 담을 수 있게 하는 것이 문제 해결의 요지였습니다. 서브 컨테이너가 마치 자료구조의 Stack과도 같은 구조를 하고 있기 때문에 두 개의 vector를 통해 어렵지 않게 해결이 가능한 문제였습니다.

 

하나 주의해야할 부분은 서브 컨테이너에 옮기다가 order에 맞게 택배 상자를 실은 다음에, 다음 차례로 실어야 하는 박스 번호가 서브 컨테이너와 메인 컨테이너에서 곧 장 꺼낼 수 없다고 하더라도 더 실을 수 있는 경우가 존재하는 것 입니다.

메인컨테이너가 비어있는게 아니라면 서브컨테이너에 다시 옮기면서 이번에 실어야 하는 박스번호를 찾아서 옮길 수 있는 경우가 존재합니다. 처음 풀이에는 저도 문제에 나와있는 테스트케이스만 보고 그대로 구현하다보니 이부분을 놓쳤지만, 채점에서 틀리는 테케가 많은것을 보고 다시 풀면서 정답을 받을 수 있었습니다. (answer가 1로 시작하는 이유는 어떤 경우라도 무조건 하나의 택배상자는 실을 수 있기 때문)

 

 

#include <string>
#include <vector>
 
using namespace std;
 
int solution(vector<int> order) {
    int answer = 1;
    
    vector<int> sub;
    vector<int> main;   // 3 1 2 5 4
    
    int start = order[0];
    
    for (int i=order.size();i>=1;i--)
    {
        main.push_back(i);  
    }
    
    for (int i=1;i<start;i++)
    {
        sub.push_back(i);
        main.pop_back();
    }
    
    int idx = 1;
    main.pop_back();
    
    //다시 왔다갔다 하는 과정이 안들어있음.
    // main   2 3 4 5
    // sub   
    // box 1 3 
    while(true)
    {        
        int cur = order[idx];
        bool flag = false;
        
        if (main.size() != 0 && cur == main[main.size()-1])
        {
            answer++;
            idx++;
            flag = true;
            main.pop_back();
            continue;
        }
        
        if (sub.size() != 0 && cur == sub[sub.size()-1])
        {
            answer++;
            idx++;
            flag = true;
            sub.pop_back();
            continue;
        }
        
        if (main.size() != 0  && cur != main[main.size()-1])
        {
            int tmp = main[main.size()-1];
            main.pop_back();
            sub.push_back(tmp);
            continue;
        }
        
        if (flag==false)
            break;
    }
    
    
    return answer;
}