📝 문제
https://www.acmicpc.net/problem/24511
문제 설명
한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해 냈다. 그 자료구조의 이름은 queuestack이다.
queuestack의 구조는 다음과 같다. 1$1$번, 2$2$번, ... , N$N$번의 자료구조(queue 혹은 stack)가 나열되어있으며, 각각의 자료구조에는 한 개의 원소가 들어있다.
queuestack의 작동은 다음과 같다.
- $x_0$을 입력받는다.
- $x_0$을 $1$번 자료구조에 삽입한 뒤 $1$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 $x_1$이라 한다.
- $x_1$을 $2$번 자료구조에 삽입한 뒤 $2$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 $x_2$이라 한다.
- ...
- $x_{N-1}$을 $N$번 자료구조에 삽입한 뒤 $N$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 $x_N$이라 한다.
- $x_N$을 리턴한다.
도현이는 길이 M$M$의 수열 C$C$를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 1$1$ 참고)
queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.
입력
첫째 줄에 queuestack을 구성하는 자료구조의 개수 N$N$이 주어진다. (1≤N≤100000$1 \leq N \leq 100\,000$)
둘째 줄에 길이 N$N$의 수열 A$A$가 주어진다. i$i$번 자료구조가 큐라면 Ai=0$A_i = 0$, 스택이라면 Ai=1$A_i = 1$이다.
셋째 줄에 길이 N$N$의 수열 B$B$가 주어진다. Bi$B_i$는 i$i$번 자료구조에 들어 있는 원소이다. (1≤Bi≤1000000000$1 \leq B_i \leq 1\,000\,000\,000$)
넷째 줄에 삽입할 수열의 길이 M$M$이 주어진다. (1≤M≤100000$1 \leq M \leq 100\,000$)
다섯째 줄에 queuestack에 삽입할 원소를 담고 있는 길이 M$M$의 수열 C$C$가 주어진다. (1≤Ci≤1000000000$1 \leq C_i \leq 1\,000\,000\,000$)
입력으로 주어지는 모든 수는 정수이다.
출력
수열 C$C$의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.
입출력
예제 입력
4
0 1 1 0
1 2 3 4
3
2 4 7
예제 출력
4 1 2
첫 번째 시도- 실패(시간 초과)
#include<iostream>
#include <deque>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
deque<pair<int, int>> dq;
int* iArray;
int iSize(0), iInput(0);
cin >> iSize;
iArray = new int[iSize];
for (int i = 0; i < iSize; ++i)
cin >> iArray[i];
for (int i = 0; i < iSize; ++i)
{
cin >> iInput;
dq.push_back(make_pair(iArray[i], iInput));
}
delete[] iArray;
cin >> iSize;
iArray = new int[iSize];
deque<pair<int, int>>::iterator iter;
for (int i = 0; i < iSize; ++i)
{
cin >> iInput;
int iTemp = iInput;
iter = dq.begin();
for (iter = dq.begin(); iter != dq.end(); ++iter)
{
if ((*iter).first == 0) // 큐 (스택은 iTemp의 변화가 없음)
swap((*iter).second, iTemp);
}
iArray[i] = iTemp;
}
for (int i = 0; i < iSize; ++i)
cout << iArray[i] << ' ';
delete[] iArray;
return 0;
}
두 번째 시도 - 성공
#include<iostream>
#include <deque>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
deque<int> dq;
int iSize(0), iInput(0);
cin >> iSize;
for (int i = 0; i < iSize; ++i)
{
cin >> iInput;
vec.push_back(iInput);
}
for (int i = 0; i < iSize; ++i)
{
cin >> iInput;
if (vec[i]) continue;
dq.push_back(iInput);
}
cin >> iSize;
for (int i = 0; i < iSize; ++i)
{
cin >> iInput;
dq.push_front(iInput);
cout << dq.back() << ' ';
dq.pop_back();
}
return 0;
}
- 이 문제를 해석해 보면, queue의 특성(FIFO) stack의 특성(LIFO)을 이해하고 풀면 된다.
✍️ 중요 포인트
- queue로 인지 되는 자료구조는 현재 가지고 있는 번호와 들어온 번호를 swap 해주면 되고
- stack으로 인지 되는 자료구조는 들어온 번호를 그대로 넘겨준다.
- 결국은 queue로 인지 되는 값만 저장해놓은 후 저장되어 있는 값은 front위치에 삽입해 주고, 마지막 번호를 출력해주면 해결된다.