245511_queuestack

문제

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 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

예제 출력 1

4 1 2

각 상태에 대한 큐스택 내부를 표현하면 다음과 같다.

초기 상태 : [1,2,3,4]
첫 번째 원소 삽입 : [2,2,3,1]
두 번째 원소 삽입 : [4,2,3,2]
세 번째 원소 삽입 : [7,2,3,4]

예제 입력 2

예제 출력 2

1 3 5

내 제출

#include <iostream>
#include <deque>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    //시간초과를 해결하기 위한 입출력 속도 향상 코드
    
	deque<int> d;
	int N, n;
	cin >> N;
	int ds[100001];
	for (int i = 0;i < N;i++) {
		cin >> ds[i];
	}

	for (int i = 0;i < N;i++) {
		int a;
		cin >> a;
		if (ds[i] == 0) {
			d.push_back(a);
		}
		//stack일 때(1일때)는 LIFO이기 때문에 새로 들어온게 바로 pop 된다.
	}
	
	cin >> n;
	for (int i = 0;i < n;i++) {
		int a;
		cin >> a;
		d.push_front(a);
		cout << d.back() << " ";
		d.pop_back();
	}
	//queue만 저장하고 stack은 저장 안함. stack인 경우에도 queue를 만나면 push front하고 back이 pop 됨.
	//전부 stack일 땐 빈 데크에 push하게 되므로 pop하는 것이 자기 자신이 됨.
	//예시를 보아도 queue의 값만 계속해 pop된다. 모두 stack인 경우엔 모두 자기 자신이 pop 된다.
}

풀이

//속도 향상 코드
일반적인 cin과 cout은 C의 scanf보다 느리다.
속도를 향상시키기 위해
ios::sync_with_stdio(false);
cin.tie(null);
cout.tie(null);
코드를 사용하였다. null 대신 0을 넣어도 된다.

//데크 사용
처음엔 스택과 큐를 사용하여 모든 과정을 브루트포스처럼 돌려 해결하였다.
답은 정확했지만 시간초과가 당연히 발생했다.
이를 해결하기 위한 방식으로 양쪽으로 입출력이 모두 가능한 데크를 사용하였다.

입출력 예제를 손으로 직접 풀이를 하다보면 알게 된다.
스택에 들어가는 값은 의미가 없는 값인 것을!!!
어차피 스택에 들어가면 돌아오는 값은 똑같다.
그래서 스택은 그냥 건너뛰는 느낌으로다가 스택 값은 아예 저장을 안했다.

이에 반해 물음이 올 수 있다.
전부 스택이면요?
이때도 그냥 데크에 푸쉬하면 팝되는 값이 본인이라
자기자신을 그대로 pop하면 된다.

분명 queuestack이지만 queue의 값만 계속해 pop되는 아이러니한 경우의 문제다.

728x90