문제 131704. 택배상자

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.

만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.

 

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

입력

• 정수 배열 order

입력 제한

• 1 ≤ order의 길이 ≤ 1,000,000
• order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.
• order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.

입력 예제

// input
[4, 3, 1, 2, 5]

// ans
2

 

풀이 방식

원하는 상자 번호가 아닌 경우 작은 컨베이어 벨트에 저장할 수 있다. 저장하는 방식을 스택(stack)으로, 먼저 넣은 상자가 가장 뒤에 있게된다. 따라서, 다음과 같이 코드가 작동해야한다.

• 컨베이어 벨트에서 다음 상자가 다음 번호를 가진 상자인지 확인한다
• 만약 다음 번호라면 해당 상자를 트럭에 실고, 다음 상자를 확인한다. 
• 만약 다음 번호가 아닌 상자라면, 작은 컨베이어 벨트에 가장 나중에 넣은 상자가 다음 번호인지 확인한다. 다음 번호상자인 경우, 해당 상자를 트럭에 싣고 그 다음 상자들이 실을 수 없는 상자가 나올 때까지 반복적으로 확인하고 싣는다.
  작은 컨베이어 벨트에서 더이상 실을 수 없는 상자가 나왔다면, 다시 컨베이어 벨트로 돌아간다.
• 컨베이어 벨트, 작은 컨베이어 벨트 모두 실을 수 있는 상자가 없을 때까지 위 과정을 반복한다.

위와 같이 과정을 코드로 구현한 다음, 트럭에 실을 상자의 개수를 저장하는 변수로 실은 상자의 개수를 추적한다면 정답을 구할 수 있다.

정답 코드 

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

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    stack<int> s;
    
    int cur_box = 1;
    
    bool find;
    for(int o : order){
       
        find = false;
        // 만약 현재 박스 번호보다 주문 번호가 높다면,
        if(cur_box < o){
            //cout << "따로 저장\n";
            while(cur_box < o){
                s.push(cur_box);
                cur_box++;
            }
            find = true;
            answer++;
            
            cur_box++;
        }
        else if(cur_box > o){
            //cout << "작은 컨베이어벨트\n";
            int box_no = s.top(); s.pop();
            if(box_no == o){
                find = true;
                answer++;
            }
            
        }
        else{
            //cout << "바로찾음\n";
            find = true;
            answer++;
            cur_box++;
        }
        
        if(!find) break;
        
    }
    return answer;
}