[ MR 02. 백준 - 24511. queuestack ]

yeahzxnn·2024년 7월 5일

24511 dequeue 덱 백준 백준24511 백준queuestack 코딩테스트 코테 코테덱 코테준비

MakingRoutine - CodingTest

목록 보기

2/7

[ MR 01. 백준 - 24511. queuestack ]

Making Routine Series : MR
02. 백준 : 24511. queuestack

습관처럼 만들기 위해 쓰는 포스트입니다!

문제

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 queuestack이다.
queuestack의 구조는 다음과 같다.
$1$ 번,
$2$ 번, ... ,
$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$ 의 수열
$C$ 를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제
$1$ 참고)
queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.

[ 입력 조건 ]

첫째 줄에 queuestack을 구성하는 자료구조의 개수
$N$ 이 주어진다. ( $1 \leq N \leq 100\,000$ )
둘째 줄에 길이 $N$ 의 수열 $A$ 가 주어진다.
$i$ 번 자료구조가 큐라면
$A_i = 0$ , 스택이라면
$A_i = 1$ 이다.
셋째 줄에 길이 $N$ 의 수열 $B$ 가 주어진다.
$B_i$ 는 $i$ 번 자료구조에 들어 있는 원소이다.
( $1 \leq B_i \leq 1\,000\,000\,000$ )
넷째 줄에 삽입할 수열의 길이 $M$ 이 주어진다.
( $1 \leq M \leq 100\,000$ )
다섯째 줄에 queuestack에 삽입할 원소를 담고 있는 길이
$M$ 의 수열 $C$ 가 주어진다.
( $1 \leq C_i \leq 1\,000\,000\,000$ )
입력으로 주어지는 모든 수는 정수이다.

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, P채널과 T채널 모두 구독하고 있는 사람의 수의 최댓값과 최솟값을 공백 하나를 사이로 두고 차례대로 출력한다.
#1 3 0
#2 5 2
#3 100 100

[ 내가 푼 답 ]

#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N,M;
    cin >> N;
    
    vector<int> type(N); // 0이면 스택, 1이면 큐
    vector<int> initial(N); //배열 각 자료구조 초기 원소값 저장
    
    for(int i=0; i<N; ++i){
        cin >> type[i];
    }
    
    for(int i=0; i<N; ++i){
        cin >> initial[i];
    }
    
    cin >> M;
    vector<int> C(M);
    for(int i=0; i<M; i++) {
        cin >> C[i]; //queuestack에 넣을 원소들의 수열
    }
    
    //자료구조를 vector of deque로 사용
    vector<deque<int>> ds(N); //각 자료구조 deque 사용해 초기화 - 큐와 스택의 기능 모두 지원
    for(int i=0; i<N; ++i) {
        ds[i].push_back(initial[i]);
    }
    
    vector<int> results; //결과값 저장할 벡터
    
    //C원소 처리
    for(int i=0; i<M; ++i){
        int current = C[i];
        for(int j=0; j<N; ++j) {
            if (type[j] == 0) {
                // 스택 (LIFO)
                ds[j].push_back(current);
                current = ds[j].back();
                ds[j].pop_back();
            } else {
                //큐(FIFO)
                ds[j].push_back(current);
                current = ds[j].front();
                ds[j].pop_front();
            }
        }
        results.push_back(current);
    }
    
    //결과값 출력
    for(int res : results) {
        cout << res << " ";
    }
    
    return 0;
}

이렇게 풀었더니 시간초과났음...

~~(승헌쓰) Retry...~~

2트 - 시간초가 안 남...

#include <iostream>
#include <deque>

using namespace std;

deque<int> dq; // 덱을 이용하여 큐와 스택의 동작을 구현
int n, m; // n: 자료구조의 수, m: 수열의 길이
bool flag[100001]; // 자료구조의 타입을 저장하는 배열, 0: queue, 1: stack

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n; // 자료구조의 수 입력
    for(int i = 0; i < n; i++){
        cin >> flag[i]; // 각 자료구조의 타입 입력
    }
    
    for(int i = 0; i < n; i++){
        int x;
        cin >> x; // 각 자료구조의 초기 원소 값 입력
        if(flag[i] == 0) // 자료구조가 큐일 때만 덱에 원소 삽입
            dq.push_back(x);
    }
    
    cin >> m; // 수열의 길이 입력
    for(int i = 0; i < m; i++){
        int y;
        cin >> y; // 수열의 각 원소 입력
        dq.push_front(y); // 덱의 앞에 새 원소 삽입
        cout << dq.back() << " "; // 덱의 뒤에서 원소를 출력
        dq.pop_back(); // 덱의 뒤에서 원소 제거
    }
    
    // 모든 자료구조가 스택일 경우에는 dq를 사용하지 않음
    // 수열의 각 원소에 대해 새 덱에 push_front 후 pop_back 과정 반복
    
    return 0;
}

덱에 대해서 다시 복습하고 가보자.

덱(Deque)이란?

덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조. 즉, 앞쪽(front)과 뒤쪽(back)에서 모두 삽입(push)과 삭제(pop) 연산가능. 덱은 스택과 큐의 기능 모두 포함!!!

덱(Deque)을 왜 쓸까?

효율적인 양방향 접근: 덱은 양쪽 끝에서 삽입과 삭제가 가능하기 때문에, 특정 상황에서 매우 효율적.
다양한 용도: 스택, 큐, 또는 둘의 혼합된 형태로 사용가능.

이 문제에서 덱(Deque)이 사용된 이유

초기 자료구조 상태 저장:

문제에서는 각 자료구조가 초기 상태로 고정되어 있고, 새로운 원소가 삽입될 때마다 덱을 이용하여 큐 또는 스택의 동작을 구현.
초기 자료구조가 큐인 경우에만 덱에 초기 값을 저장하여 이후 연산에서 사용.

수열 처리:

각 수열 원소에 대해 덱의 앞쪽(front)에 값을 삽입하고, 덱의 뒤쪽(back)에서 값을 빼내어 출력.