[Programmers, C++]#Level2_택배 상자, 큐, 스택, 선형 자료구조

#1. 문제

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

 

---

 

#2. 풀이

 

1. 스택

[자료 구조]#0_선형 자료구조

스택은 후입선출 방식으로 동작하는 선형 자료구조로, 데이터 목록의 한쪽 끝에서만 삽입/삭제 작업이 이루어지는 특징이 있습니다. 

 

2. 큐

[자료 구조]#0_선형 자료구조

큐는 선입선출 방식으로 동작하는 선형 자료구조로, 데이터 목록의 한 쪽한쪽 끝에서는 삽입 작업만, 다른 한쪽에선 삭제 작업만 수행하는 특징이 있습니다. 

 

3. 큐에 상자를 모두 다 넣고, 원하는 순서의 상자가 나올 때 까지 스택에 넣자!

1. 먼저, 큐 자료구조에 모든 상자를 다 삽입해줍니다. 그리고, 별도의 스택을 선언해 줍니다.
2. 루프를 돌며 현재 원하는 순서의 상자가 나올 때까지 큐에서 상자를 pop()하고, 스택에 차례대로 삽입해 줍니다.
3. 2번 작업을 통해 큐의 front()에 원하는 순서의 상자가 나왔다면 카운트, q.pop(), 다음 원하는 순서로 넘어갑니다.
4. 2번 작업을 통해 큐의 front()에 원하는 순서의 상자가 없다면, 스택을 순회하며 원하는 상자가 있는지 확인해 줍니다. 이때, 스택에도 없을 경우 루프를 끝내고 정답을 반환해 줍니다.

 

---

 

#3. 코드

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

using namespace std;

int solution(vector<int> order) {
    int ans = 0;

    queue<int> q;
    stack<int> s;

    for(int i=1; i<=(int)order.size(); ++i) {
        q.push(i);
    }

    int index = 0; // order를 위한 인덱스
    while(index < order.size()) {
        // 큐에서 원하는 순서의 상자가 나올 때까지 스택으로 옮김
        while(!q.empty() && q.front() != order[index]) {
            s.push(q.front());
            q.pop();
        }

        // 큐에 원하는 상자가 있다면, 처리
        if(!q.empty() && q.front() == order[index]) {
            ans++;
            q.pop();
            index++;
        }
        // 큐에 원하는 상자가 없는 경우, 스택에서 처리할 수 있는지 확인
        else {
            if(!s.empty() && s.top() == order[index]) {
                ans++;
                s.pop();
                index++;
            } else {
                // 스택에서도 처리할 수 없는 경우 종료
                break;
            }
        }

        // 스택에 있는 상자들을 계속해서 처리할 수 있는지 확인
        while(!s.empty() && index < order.size() && s.top() == order[index]) {
            ans++;
            s.pop();
            index++;
        }
    }

    return ans;
}

 

---