[Baekjoon] 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$)

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

---

😂출력

수열
$C$의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.

---

🤣예제

예제 입력 1 
4
0 1 1 0
1 2 3 4
3
2 4 7
예제 출력 1 
4 1 2

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

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

예제 입력 2 
5
1 1 1 1 1
1 2 3 4 5
3
1 3 5
예제 출력 2 
1 3 5

---

😃출처

• Camp > ICPC Sinchon Algorithm Camp > 2022 ICPC Sinchon Winter Algorithm Camp Contest > 초급 C번
• 문제를 검수한 사람: gratus907, Green55, gumgood, kyo20111, lky7674, mjhmjh1104, tony9402
• 문제를 만든 사람: swoon

---

😄알고리즘 분류

• 자료 구조
• 스택
• 덱
• 큐

---

😎나의풀이

머리에 그려진대로 이중반복을 하다 시간초과를 겪었다.. 제한 시간은 1초였으니까 당연한 결과이지만
문제를 유심히 보면 특이사항이 있다.
바로

• 큐형식의 자료는 큐 형식의 입력FIFO(좌측입력)
• 스택형식은 볼 필요 없음(어차피 입력된 값을 모두 튕겨낼 뿐)
• 순열 C의 배열은 스택 형식의 입력FILO(우측입력)

결과는 입력된 형식에서 좌측부터 추출하면 된다.

이유는 풀이에 써있지만, 큐 형식의 요소에 입력값이 밀리면서 가장 우측의 값이 출력되는 형식이므로 스택은 볼 필요가 없고
만약 모든 값이 스택이라면 넣는 족족 튕겨내기에 우선 입력한 순으로 출력되게 된다.

class Node {
    constructor(value) {
        this.value = value
    }
    prev = null
    next = null
}

class Deque {
    left = null
    right = null
    size = 0
    leftInsert(val) {
        const curNode = new Node(val)
        this.size += 1
        if(!this.left || !this.right) {
            this.left = curNode
            this.right = curNode
        } else {
            curNode.next = this.left
            this.left.prev = curNode 
            this.left = curNode
        }
    }
    rightInsert(val) {
        const curNode = new Node(val)
        this.size += 1
        if(!this.left || !this.right) {
            this.left = curNode
            this.right = curNode
        } else {
            curNode.prev = this.right
            this.right.next = curNode 
            this.right = curNode
        }
    }
    leftExtract() {
        if(!this.left) return
        const popedVal = this.left.value
        this.size -= 1
        if(this.left.next) {
            this.left = this.left.next
            this.left.prev = null    
        } else {
            this.left = null
            this.right = null
        }
        return popedVal
    }
}

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split("\n")
const deque = new Deque()
const C = input.pop().split(" ") // ["2", "4", "7"]
const CLen = input.pop()
const B = input.pop().split(" ") // ["1", "2", "3", "4"]
const A = input.pop().split(" ") // ["0", "1", "1", "0"]
const ABLen = Number(input.pop())
const result = []
// 타입이 '큐' 인 요소 중 뒤에 있는 요소가 가장 먼저 출력 됨(큐의 요소들이 밀리면서 가장 우측에서 출력)
for(let i = 0 ; i < ABLen ; i ++) {
    if(A[i] === '0') deque.leftInsert(B[i])
}
// 입력이 그 다음 입력된 순으로 출력됨(타입이 '큐' 인 요소의 자리에 순서대로 재입력되기 때문)
for(let i = 0 ; i < CLen ; i ++) {
    deque.rightInsert(C[i])
    result.push(deque.leftExtract())
}

console.log(result.join(" "))