[BOJ S3][C++] 백준 24511번: queuestack (시간초과를 해결해보자)

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

24511번: queuestack

 

문제

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

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

queuestack의 작동은 다음과 같다.

•  x0$x_0$을 입력받는다.
•  x0$x_0$을 1$1$번 자료구조에 삽입한 뒤 1$1$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x1$x_1$이라 한다.
•  x1$x_1$을 2$2$번 자료구조에 삽입한 뒤 2$2$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x2$x_2$이라 한다.
• ...
•  xN−1$x_{N-1}$을 N$N$번 자료구조에 삽입한 뒤 N$N$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 xN$x_N$이라 한다.
•  xN$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에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.

 

풀이

시간초과가 나지 않기 위해서는 절대 말그대로 stack 과 queue를 구현하면 안될 것 같았다.

 

예제 두개를 바탕으로 직접 손으로 단계별 변화를 그리면서 규칙을 찾아냈는데,

1. 결국 스택은 갓 삽입한 값을 바로 리턴하므로 무시해도 된다.

2. stackqueue라고 어려운 이름을 넣긴 했지만 stackqueue[i]를 i번째 자료구조가 반환하는 값이라고 봤을때, stackqueue 자체는 하나의 큐다.

3. 결론적으로 n개의 인풋들중 스택에 들어가는 인풋들은 무시하고 큐에 들어가는 인풋들만 stackqueue라는 큐에 역순으로 넣어준뒤

4. m개의 인풋들을 stackqueue라는 큐에 순서대로 넣고 front를 반환하면 됨.

 

이때 결국 queue와 같다고 말하긴 했지만, n개의 인풋을 넣을때 역순으로 넣어줘야하기 때문에 양방향 자료구조인 deque를 이용했다

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    deque<int> stackqueue;

    int  n, m, input;
    cin >> n;
    vector<int> isQueue(n);
    for(int i=0; i<n; i++)
        cin >> isQueue[i];
    for(int i=0; i<n; i++) {
        cin >> input;
        if(isQueue[i]==0) // 큐일때만 연산
            stackqueue.push_front(input);
    }
            
    cin >> m;
    for(int i=0; i<m; i++){
        cin >> input;
        stackqueue.push_back(input);
        cout << stackqueue.front() << " ";
        stackqueue.pop_front();
    }
    
    return 0;
}

/*
 */

 

시행착오

처음에는 문자 그대로 stackqueue 배열 안에 스택과 큐를 구현해서 수동으로 계산시켰다 -> but 시간초과

시간을 줄이기 위해 스택인 경우에는 연산을 생략하고 큐일때만 연산하도록 했다 -> however 시간초과!

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int  n, m, element, input;
    cin >> n;
    vector<queue<int>> stackqueue(n, queue<int>());
    // 스택일때는 삽입하는 값과 리턴하는 값이 같으므로 굳이 스택을 구현할 필요가 없다.
    vector<int> isStack(n);
    for(int i=0; i<n; i++)
        cin >> isStack[i];
    for(int i=0; i<n; i++) {
        cin >> element;
        stackqueue[i].push(element);
    }
    
    cin >> m;
    for(int i=0; i<m; i++){
        cin >> input;
        
        for(int j=0; j<n; j++) {
            if(!isStack[j]) { // 큐일때만 연산
                stackqueue[j].push(input);
                input = stackqueue[j].front();
                stackqueue[j].pop();
            }
        }
        cout << input << " ";
        
    }
    
    return 0;
}

/*
 */

시간을 더 줄이고 싶어서 아예 스택이랑 큐를 구현하지 않았다 -> nevertheless 시간초과

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int  n, m, input;
    cin >> n;
    vector<int> stackqueue(n);
    vector<int> isStack(n);
    for(int i=0; i<n; i++)
        cin >> isStack[i];
    for(int i=0; i<n; i++)
        cin >> stackqueue[i];
    
    cin >> m;
    for(int i=0; i<m; i++){
        cin >> input;
        
        for(int j=0; j<n; j++) {
            if(isStack[j]==0) { // 큐일때만 연산
                int temp = stackqueue[j];
                stackqueue[j] = input;
                input = temp;
            }
        }
        cout << input << " ";
    }
    
    return 0;
}

/*
 */