[백준BOJ] #24511 Questack (C++)

https://www.acmicpc.net/submit/24511

queuestack 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

1024 MB (추가 메모리 없음)

14100

5062

4254

34.895%

문제

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 queuestack이다.

queuestack의 구조는 다음과 같다. 1$1$번, 2$2$번, ... , 𝑁$N$번의 자료구조(queue 혹은 stack)가 나열되어있으며, 각각의 자료구조에는 한 개의 원소가 들어있다.

queuestack의 작동은 다음과 같다.

•  𝑥0$x_0$을 입력받는다.
•  𝑥0$x_0$을 1$1$번 자료구조에 삽입한 뒤 1$1$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 𝑥1$x_1$이라 한다.
•  𝑥1$x_1$을 2$2$번 자료구조에 삽입한 뒤 2$2$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 𝑥2$x_2$이라 한다.
• ...
•  𝑥𝑁−1$x_{N-1}$을 𝑁$N$번 자료구조에 삽입한 뒤 𝑁$N$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 𝑥𝑁$x_N$이라 한다.
•  𝑥𝑁$x_N$을 리턴한다.

도현이는 길이 𝑀$M$의 수열 𝐶$C$를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 1$1$ 참고)

queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 queuestack을 구성하는 자료구조의 개수 𝑁$N$이 주어진다. (1≤𝑁≤100000$1 \leq N \leq 100\,000$)

둘째 줄에 길이 𝑁$N$의 수열 𝐴$A$가 주어진다. 𝑖$i$번 자료구조가 큐라면 𝐴𝑖=0$A_i = 0$, 스택이라면 𝐴𝑖=1$A_i = 1$이다.

셋째 줄에 길이 𝑁$N$의 수열 𝐵$B$가 주어진다. 𝐵𝑖$B_i$는 𝑖$i$번 자료구조에 들어 있는 원소이다. (1≤𝐵𝑖≤1000000000$1 \leq B_i \leq 1\,000\,000\,000$)

넷째 줄에 삽입할 수열의 길이 𝑀$M$이 주어진다. (1≤𝑀≤100000$1 \leq M \leq 100\,000$)

다섯째 줄에 queuestack에 삽입할 원소를 담고 있는 길이 𝑀$M$의 수열 𝐶$C$가 주어진다. (1≤𝐶𝑖≤1000000000$1 \leq C_i \leq 1\,000\,000\,000$)

입력으로 주어지는 모든 수는 정수이다.

출력

수열 𝐶$C$의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.

 

 

접근 방식 

참말로... 백준 풀다보면 웃긴 글 본 것 마냥 웃을 때가 있다. 한가롭게 놀다가 자료구조를 왜 생각하는지

여튼 이 문제는 스택과 큐가 동시에 등장하지만 쫄 필요가 없다!!!! 

 

스택, 큐를 1,0으로 입력받는 점에서 bool 타입으로 뭔가를 구현해야겠구나~~ 싶은 생각이 들거고,

스택의 경우 원소를 넣자마자 결국 빼는 건 원소 자기자신이니 무시해도 된다.

결국, 스택은 무시하고 큐의 경우만 생각해주면 되는데, 큐 없이 스택으로만 이뤄진 경우에는 입력 순서대로 원소를 리턴하기에 큐가 비어있을 때, 큐에 원소가 하나라도 있을 때 두 가지 경우로 나눴다. 

 

스택, 큐, 덱의 개념을 모두 알아둬야 하지만 문제 풀 때는 보통 덱으로 푸는 편이고, 이 문제도 역시 덱으로 풀었다.

 

 

정답 코드 

#include<iostream>
#include<deque>
#include<vector>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//0, 1 -> bool타입 의심 
	int n; 
	bool flag[100000]; 
	deque<int> d; 
	int elem; 


	cin >> n;
	int o=0; 
	for (size_t i = 0; i < n; i++)
	{
		cin >> flag[i]; 
		if (flag[i] == 1)
			o++; // stack 있다는 뜻
	}
	
	for (size_t  i = 0; i <n; i++)
	{
		cin >> elem; 
		if (flag[i] == 0)
			d.push_front(elem); 
	}

	int b;
	cin >> b;
	for (size_t i = 0; i < b; i++)
	{
		cin >> elem; 
		if (!d.empty()) {
			d.push_back(elem);
			cout << d[0] << " ";
			d.pop_front();
		}
		else {
			cout << elem << " ";
		}
	}

	
}