[백준/C++] 24511번: queuestack

문제 설명

 

 

● 문제 링크: http://www.acmicpc.net/problem/24511

 

 

설명

입력된 숫자들을 받아 queue와 stack 구조 체인을 만든 후에, 입력된 숫자를 이 체인에 통과시켰을 때의 결과 값을 출력하는 문제입니다.

예를 들어, 세 줄에 걸쳐 다음과 같은 숫자들이 입력되었다고 생각해 봅시다.

 

구조 체인의 크기: 6
queue인지 stack인지 구별하는 플래그: 0, 1, 1, 0, 1, 0
각각의 구조 안에 들어있는 요소 값: 32, 22, 7, 103, 3, 29

 

queuestack 구조 체인

 

그럼 위와 같은 queue - stack 체인을 도식화할 수 있을 것입니다.
그다음 테스트 할 숫자들을 M개 받아들여 체인을 통과시켰을 때의 결과 값들을 출력하면 됩니다.

그런데, 스택에 데이터를 입력하고 원소를 pop 하면, 맨 위에 데이터를 입력하고 다시 맨 위의 데이터를 출력하는 것이기 때문에 결과 값의 변화가 없습니다.
그래서 무의미한 stack 구조를 제거하면 다음과 같이 간단해집니다.

 

수정된 queuestack 구조 체인

 

이제 위 이미지를 봤을 때, 하나의 queue가 작동하는 것과 똑같다는 것을 알게 된다면 문제 해결입니다.
그런데, 각각의 queue가 있는 상태에서 데이터를 입출력하면 시간이 부족하기 때문에 반드시 하나의 queue로 합치는 것이 필요합니다.

그리고, 또 한 가지 주의할 것은 각각의 구조 안에 들어있는 요소 값들을 하나의 queue에 옮길 때, 먼저 입력된 것이 먼저 출력되기 때문에 값들의 순서를 뒤집어야 한다는 것이다.

[백준/C++] 18258번: 큐 2 ( queue 자료 구조 사용하기 )

 

 

 

이 글과 관련 있는 글들

28278번: 스택 2 ( stack 자료구조 사용하기 )

 

 

소스 코드

#include <iostream>
#include <queue>
using namespace std;

#define MAX_QST 100000

bool flags[MAX_QST];

int queNum = 0;
int queElem[MAX_QST];

int main() {

    ios::sync_with_stdio(false);	// 처리 시간을 단축하기 위해서
    cin.tie(NULL);

    int N, M, num;
    queue<int> que;

    cin >> N;
    
    for(int i = 0; i < N; i++){
        cin >> num;
        flags[i] = num;	// queue와 stack 구분 flag
    }

    for(int i = 0; i < N; i++){
        cin >> num;

        if ( !flags[i]){    // queue
           queElem[queNum] = num;
           queNum++;
        }
    }

    for(int i =queNum-1; i >=0; i--){   // 요소 값의 순서를 뒤집는다
        num = queElem[i];
        que.push(num);
    }

    cin >> M;
    
    for(int i = 0; i < M; i++){
        cin >> num;
        
        que.push(num);
        
        num = que.front();
        que.pop();

        cout << num << " ";
    }

    return 0;
}