[Silver III] queuestack - 24511

JYC·2025년 2월 2일

C++백준 알고리즘 문제

[BAEKJOON]

목록 보기

100/102

queuestack 문제 (https://www.acmicpc.net/problem/24511)

문제를 처음 읽을 경우 “?” 라는 생각이 들 수 있습니다. 제가 그랬거든요 ㅎ;

문제 설명을 다시 한번 차근차근 읽어보시고 와주세요!

예제 1을 통해 어떻게 동작하는지 한번 확인해보겠습니다.

기본적인 입력입니다.

자료구조의 개수 N= 4이고

두번째 줄엔 i번 자료구조가 큐인지 스택인지 써있습니다. 즉

이런 식으로 구성이 될겁니다.

그 후 삽입할 수열의 길이 M = 3이고

2 4 7 이 들어오게 됩니다.

즉 먼저 0번 자료구조(큐) 에 2라는 값이 PUSH될겁니다. 그리고는 pop됩니다.

이런 식으로 바뀌겠죠? (큐는 선입선출: 먼저 들어온 값이 먼저 나간다)

그리고 1번 자료구조인 스택에 1이라는 값이 push되어 넘어가게 될겁니다.

하지만 여기서 중요한 점은 스택은 선입후출 즉 먼저 들어온 값이 나중에 나가게 됩니다.

그 말은 즉 스택은 기존의 값 변화 없이 새로 들어온 값이 2번 자료 구조 스택으로 pop된다는 겁니다.

그렇기에 1이라는 값이 빠져나가게 됩니다.

2번도 스택이므로 똑같이?

새로 들어왔던 값이 또 빠이빠이 하고 나가게 됩니다.

이제 3번에서는 자료구조가 큐이므로 어떤 값이 빠져나가나요?

바로 먼저 들어왔던 4라는 값이 나가게 됩니다.

그렇기에 예제 출력 1에서

4 1 2

첫번째 값이 4가 되는 것입니다!

이런 식으로 쭉쭉 이어나가게 되는 과정이라고 설명드릴 수 있을 거 같습니다!

여기서 이상한 점을 느끼시면 좋을 거 같습니다.

막말로 스택은 하는 일이 없습니다!

이 말이 바로 문제의 핵심입니다.

다시 문제를 한번 볼까요?

시간제한은 1초입니다.

그리고 우리가 넣을 수 있는 최대 자료구조의 개수 N은?

10만개까지입니다.

이 말이 의미하는 바가 뭔가요? 라고 한다면

100000 X 100000 은 10000000000 즉 10억입니다.

제가 ppt에서 간단하게 코멘트로 적어두긴 했지만 다시 한번 말씀드리자면

대략 컴퓨터가 1억 번의 연산을 하기 위해서는 1초 정도의 시간이 필요합니다.

고로 적어도 우리는 O(N^2)이 되선 안됩니다.

이걸 생각하고 스택이 필요없다 라는 걸 인지하신다면 풀이가 좀 간소화되고, 그만큼의 시간복잡도가 줄어들게 됩니다.

여기서 말하는 스택이 필요없다 라는 말을 조금 디테일하게 설명드리는 겸 문제 풀이를 먼저 올려드리겠습니다.

문제 코드

#include <iostream>
#include <queue>

using namespace std;

queue<int> queue_storage;      // 큐 역할을 하는 변수
bool is_stack[100000];         // 데이터가 스택에 들어가야 하는지 여부를 나타내는 배열

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;                     // 기존 데이터의 개수
    int m;                     // 새로 삽입할 데이터의 개수
    int value[100001] = {};                 // 입력값
    cin >> n;

    // 데이터가 스택에 들어가야 하는지 여부 입력
    for (int i = 0; i < n; i++) {
        cin >> is_stack[i];
    }

    // 기존 데이터 입력
    for (int i = 0; i < n; i++) {
        cin >> value[i];
    }

    //데이터 처리
    for (int i = n-1; i >= 0; i--) { //역순으로 입력받은 데이터를 처리해야 함!!
        if (!is_stack[i]) {  // 0이라면 값 넣어주기 
            queue_storage.push(value[i]);
        }
    }

    // 새 데이터 입력 +  결과 출력
    int num;
    cin >> m;

    for (int i = 0; i < m; i++) {
        cin >> num;
        queue_storage.push(num);
        cout << queue_storage.front() << " ";
        queue_storage.pop();
    }

    return 0;
}

해당 풀이에서는 Stack 을 사용하지 않습니다.

먼저 기본적인 데이터 입력을 실행합니다.

그 후

    //데이터 처리
    for (int i = n-1; i >= 0; i--) { //역순으로 입력받은 데이터를 처리해야 함!!
        if (!is_stack[i]) {  // 0이라면 값 넣어주기 
            queue_storage.push(value[i]);
        }
    }