queuestack 성공

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

1 초 (추가 시간 없음)

1024 MB (추가 메모리 없음)

14100

5062

4254

34.895%

문제

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

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

queuestack의 작동은 다음과 같다.

𝑥0을 입력받는다.
𝑥0을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 𝑥1이라 한다.
𝑥1을 2번 자료구조에 삽입한 뒤 2번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 𝑥2이라 한다.
...
𝑥𝑁−1을 𝑁번 자료구조에 삽입한 뒤 𝑁번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 𝑥𝑁이라 한다.
𝑥𝑁을 리턴한다.

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

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

입력

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

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

셋째 줄에 길이 𝑁의 수열 𝐵가 주어진다. 𝐵𝑖는 𝑖번 자료구조에 들어 있는 원소이다. (1≤𝐵𝑖≤1000000000)

넷째 줄에 삽입할 수열의 길이 𝑀이 주어진다. (1≤𝑀≤100000)

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

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

출력

수열 𝐶의 원소를 차례대로 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 << " ";
		}
	}

	
}