[백준/BOJ] 24511번 queuestack (C/C++)

백준 온라인 저지(BOJ) 24511번 queuestack
https://www.acmicpc.net/problem/24511

24511번: queuestack

* 사용언어 : C언어, C++
 

1. 문제

각각 1개의 원소만 있는 queue 또는 stack이 N개 연달아 나열되어 있고, 이를 queuestack 자료구조라 함
queuestack에 숫자가 들어오면 1번부터 N번까지 순차적으로 push & pop을 반복하며 다음 자료구조로 값을 넘겨줌
M개의 숫자를 순서대로 queuestack에 넣어줄 때의 return값을 순서대로 출력

 

2. 풀이

문제 설명이 복잡하니 예제 입력1을 기준으로 문제 이해부터 해보겠습니다.
 
(4) → 4개의 queue or stack이 나열되어 있습니다.
(0 1 1 0) → 1, 4번은 queue이고 2, 3번은 stack입니다.
(1 2 3 4) → 1번 queue에는 1, 2번 stack에는 2, ... 와 같이 원소가 각각 1개 씩 들어있고, 이 전체를 queuestack이라고 합니다.
(3) → 3개의 숫자를 순서대로 위 queuestack에 입력합니다.
(2 4 7) → 순서대로 2, 4, 7이고 이 때 return 값을 순서대로 출력합니다. → (4 1 2)
 
 
문제가 이해가 됐다면 해당 문제를 어떻게 구현하고 풀지 고민해봅니다.
가장 쉬운 방법은 실제로 queue와 stack이 동작하는 방식을 그대로 구현하는 것 입니다.
각 자료구조가 queue인지 stack인지 입력으로 주어지기 때문에 if ~ else로 구현하면 됩니다.
 

그렇게 예제 입력의 [초기 상태], [첫 번째 원소 삽입], ... 를 살펴보다가 stack의 원소는 바뀌지 않는다는 것을 확인했습니다.
생각해보면 당연한게, LIFO 구조인 stack에 1개의 원소를 넣었다가 1개의 원소를 빼니 넣은 숫자가 그대로 넘어가게 됩니다.
 
그래서 queue, stack을 일일히 구현하지 않고 queue에 해당되는 숫자들만 추려서 새로운 queue에 넣었습니다.
그리고 해당 queue에 M개의 입력을 순서대로 head에 넣고, tail에서 빼는 FIFO 방식으로 문제를 쉽게 풀었습니다.
 
단, N개의 자료구조를 통해 추려낸 숫자들은 queue에 거꾸로 들어가 있어야 합니다.
(예제 입력 1 기준, 4가 먼저 나오고 그 다음에 1이 나와야 하므로)
따라서 N개의 자료구조에서 queue의 원소만 추려서 새로운 queue에 담을 때는 역순으로 진행해줍니다.
 
이후 M개의 입력을 처리하는 과정은 일반적인 queue와 동일합니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
24511_queuestack
2380KB	72ms
*/
#include <cstdio>

const int LM = 100000;
const int QLM = LM * 2;
int N, M, h, t;

char a[LM];
int b[LM];
int q[QLM];

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d", &a[i]);
	for (int i = 0; i < N; ++i) scanf("%d", &b[i]);

	for (int i = N - 1; i >= 0; --i) {
		if (a[i]) continue;
		q[t++] = b[i];
	}

	scanf("%d", &M);
	for (int i = 0; i < M; ++i) {
		scanf("%d", &q[t++]);
		printf("%d ", q[h++]);
	}
	return 0;
}