오늘 한 내용

---

• C++ 코드카타
• 언리얼 Collision, Trace, Damage 강의 수강
• Ch3 개인 프로젝트

코드카타 문제

---

오늘의 코드카타 문제는 다음과 같다.
프로그래머스(택배상자): https://school.programmers.co.kr/learn/courses/30/lessons/131704

지문이 프로그래머스 답지 않게 너무 길었는데, 요약하자면 다음과 같다.

1. 영재는 차례대로 오는 메인 컨테이너에서 1 ~ n까지의 택배 상자를 꺼낼 수 있다.
2. 택배를 보내는 순서에 맞게 트럭에 택배 상자를 올려야 한다.
3. 택배를 보내는 순서와 상자 번호가 맞지 않으면, 뒤에서만 꺼낼 수 있는 보조 컨테이너에 임시 보관 한다.
4. 만약 특정 순서에 해당하는 박스가 보조 컨테이너에 맨 뒤나, 메인 컨테이너에 맨 앞에 위치하지 않으면, 더 이상 택배 상자를 옮기지 않는다.

지문이 좀 길었을 뿐, 문제가 직관적인 힌트를 주고 있다.

• 메인 컨테이너는 차례대로 택배 상자가 오므로, 큐로 관리한다.
• 보조 컨테이너는 뒤에서부터 꺼낼 수 있으므로, 스택으로 관리한다.

첫 번째 예시인 [4, 3, 1, 2, 5]의 상황이라고 가정하자.
처음에는 메인 컨테이너에 1~5까지의 택배 상자가 배치되어 있다.

처음 순서는 4번 택배 상자를 먼저 올려야 하므로, 1, 2, 3번 택배 상자를 보조 컨테이너에 싣고 4번 상자를 올려놓는다.

그 다음 순번인 3번은 보조 컨테이너에서 맨 뒤에 위치하므로, 바로 꺼내서 올려놓는다.

그 다음 순번인 1번은 보조 컨테이너의 뒤에서나, 메인 컨테이너의 앞에서나 1번 택배 상자가 없으므로 그대로 트럭은 출발한다.

이때, 중요한 부분은 어디 컨테이너부터 상자를 꺼낼 지가 문제이다.
만약, 메인 컨테이너부터 상자를 꺼낸다면 위의 예제처럼 3을 꺼내야 할 때 보조 컨테이너 맨 뒤에 위치해있음에도 불구하고 5를 옮겨버려서 문제가 발생한다.

즉, 보조 컨테이너 -> 메인 컨테이너 순으로 확인해야 한다.

#include <string>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    stack<int> sub_container; // 보조 컨테이너
    queue<int> main_container; // 메인 컨테이너
    
    for (int i = 0; i < order.size(); ++i)
    {
        main_container.push(i + 1); // 1 ~ n만큼의 상자를 채워넣기
    }
    
    for (int i = 0; i < order.size(); ++i)
    {
        int cur_order = order[i];
        // 보조 컨테이너부터 확인
        if (!sub_container.empty() && sub_container.top() == cur_order)
        {
            answer++;
            sub_container.pop();
            continue;
        }
        // 보조에도 없다면 메인에서 계속 꺼내보기
        while(!main_container.empty() && cur_order != main_container.front())
        {
            sub_container.push(main_container.front());
            main_container.pop();
        }
        
        if (!main_container.empty() && main_container.front() == cur_order)
        {
            answer++;
            main_container.pop();
            continue;
        }
        // 여기까지 오면 보조/메인 둘 다 없는 것이므로 바로 트럭 출발하기
        break;
    }
    
    return answer;
}