[C++] 택배상자

[문제]

코딩테스트 연습 - 택배상자 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

처음에 문제를 읽으면 잘 이해가 안 될 수 있지만 이해를 하면 쉬운 문제이다.

 

문제 중 하나였던 [4,3,1,2,5]를 예시로 문제를 풀어보면

우선은 1부터 5까지 순서가 나열되어 있는 컨베이어 벨트가 있다고 보자.

이제 여기서 1부터 순서대로 뽑아서 트럭에 [4,3,1,2,5]의 순서대로 넣으면 된다.

트럭에 해당 순서대로 넣기 위해서 보조 컨베이어 벨트를 사용해보자.

이와 같이 순서대로 처음 컨베이어 벨트에서 나온 물건들은 보조 컨베이어 벨트에 순서대로 들어가서 제일 늦게 들어간 물건이 제일 먼저 나오는 (LIFO) 의 형태를 취하고 있다.

 

트럭에서 원하던 순서는 [4,3,1,2,5]였으니 기본에서 4를빼고 보조에서 3을 빼면

이와 같이 되어서 더 이상 진행을 할 수가 없다. 그러면 총 2개의 물건을 진행이 가능했으니 answer = 2 가 나온다.

 

stack을 이용해서 쉽게 풀 수가 있었고 자세한 부분은 코드를 참고하길 바란다.

[회고]

처음에 문제에서 도대체 무슨 소리인가 하고 헷갈렸는데 예전에 백준에서 비슷하게 풀었던 문제가 있어서 그나마 쉽게 접근이 가능했다.

stack 문제들은 가끔씩 코테에 나오는 복습할겸 가끔씩 풀어보자.

[코드]

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

int solution(vector<int> order) {
    int answer = 0;
    //1,2,3,4,5... 순으로 컨테이너 벨트에 있음.
    //이제 이 순서를 order에 맞춰서 truck 안에 넣고 싶음.
    //보조 컨테이너 벨트를 활용 가능.
    
    int cnt = 0;
    stack<int> belt;
    for(int i = 1; i<= order.size();i++){
        if(i != order[cnt]){
            belt.push(i);
            continue;
        }
        cnt++;
        answer++;
        while(belt.size() > 0 && belt.top() == order[cnt]){
            belt.pop();
            cnt++;
            answer++;
        }
    }
    
    return answer;
}