Programmers: 택배상자 (C++)

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

프로그래머스

---

Level: 2

Solved By: Stack, Implementation

 

오랜만에 프로그래머스 문제를 풀었습니다. 2~3문제 정도 푸니 순위가 80,000 정도 확 오르네요..

무엇보다 프로그래머스는 항상 느끼지만 독해력과 구현력을 집중적으로 요구하는 듯합니다.

 

order가 주어지면 이 배열을 우선 다른 배열로 바꾸어주었습니다. order가 index:순서, value:위치를 나타냈다면 이해하기 쉽게 직관적으로 v를 index:위치, value: 순서로 바꾸어주었습니다.

 

그리고, 스택 2개를 선언하여 하나는 보조 컨테이너, 다른 하나는 트럭을 만들어주었습니다. 트럭 스택에는 현재 트럭에 담겨있는 원소들을 보여주었고, top이 무엇인지에 따라 물건을 담을 수 있는지 없는지 판별했습니다. 그와 동시에 트럭에 담을 수 없는 물건은 보조 컨테이너 스택에 넣어주었습니다. 이를 반복하여 물건이 주어질 때, 보조 컨테이너에서 꺼내어 트럭에 넣을 수 있는지도 판별하여 문제를 풀 수 있었습니다.

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

int solution(vector<int> order) {
    int answer = 0;
    
    vector<int> v(order.size());
    
    for(int i = 0; i < v.size(); i++){
        v[order[i] - 1] = i + 1;
    }
    
    //for(auto i : v) cout << i << ' ';
    
    
    stack<int> bojo;
    stack<int> truck;
    for(int i = 0; i < v.size(); i++){
        if(truck.empty() && v[i] == 1){
            answer++;
            truck.push(v[i]);
        }
        else if(!truck.empty() && truck.top() + 1 == v[i]){
            answer++;
            truck.push(v[i]);
        }
        else{
            bojo.push(v[i]);
        }
        
        while(!bojo.empty() && !truck.empty() && bojo.top() == truck.top() + 1){
            truck.push(bojo.top());
            bojo.pop();
            answer++;
        }
    }
    
    
    return answer;
}