[백준 / C언어] Day21. queuestack (24511)

2024. 06. 07 - 코딩테스트 스터디 Day21

 

 

01. 문제

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

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

queuestack의 작동은 다음과 같다.

•  x₀을 입력받는다. 
•  x₀을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 원소를 pop한다. 그때 pop 된 원소를 x₁이라 한다.
•  x₁을 2번 자료구조에 삽입한 뒤 2번 자료구조에서 원소를 pop한다. 그때 pop 된 원소를 x₂이라 한다.
• ...
•  x_N-1을 N번 자료구조에 삽입한 뒤 N번 자료구조에서 원소를 pop한다. 그때 pop 된 원소를 x_N이라 한다.
•  x_N을 리턴한다.

도현이는 길이 M의 수열 C를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 1 참고)

queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해 보자.

 

 

02. 입력

첫째 줄에 queuestack을 구성하는 자료구조의 개수 N이 주어진다. (1≤𝑁≤100000)

둘째 줄에 길이 N의 수열 A가 주어진다. 𝑖번 자료구조가 큐라면 𝐴𝑖=0, 스택이라면 𝐴𝑖=1이다.

셋째 줄에 길이 N의 수열 B가 주어진다. 𝐵𝑖는 𝑖번 자료구조에 들어 있는 원소이다. (1≤𝐵𝑖≤1000000000)

넷째 줄에 삽입할 수열의 길이 M이 주어진다. (1≤𝑀≤100000)

다섯째 줄에 queuestack에 삽입할 원소를 담고 있는 길이 M의 수열 C가 주어진다. (1≤𝐶𝑖≤1000000000)

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

 

 

03. 출력

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

 

 

04-1. 예제 입력 1

4
0 1 1 0
1 2 3 4
3
2 4 7

 

 

04-2. 예제 출력 1

4 1 2

 

 

 

05-1. 예제 입력 1

5
1 1 1 1 1
1 2 3 4 5
3
1 3 5

 

 

05-2. 예제 출력 1

1 3 5

 

 

06. 풀이 및 답

이번 문제는 문제를 이해하는 것이 조금 오래 걸렸다 ^_^;;

오늘도 그림을 그려보았다.

 

우선 초기 상태는 위와 같다.

입력받은 수열 A가 [0, 1, 1, 0] 이므로 순서대로 큐, 스택, 스택, 큐 자료구조이다.

입력받은 수열 B가 [1, 2, 3, 4] 이므로 각 자료구조에 순서대로 하나씩 들어간다.

 

첫 번째로 입력받은 원소 '2'를 1번 자료구조인 큐에 push 한 뒤, 원래 들어있던 '1'을 pop 한다.

pop 된 '1'을 바로 다음 자료구조인 2번 자료구조 스택에 push 하고, 다시 pop 한다.

pop 된 '1'을 바로 다음 자료구조인 3번 자료구조 스택에 push 하고, 다시 pop 한다.

pop 된 '1'을 바로 다음 자료구조인 4번 자료구조 큐에 push 하고, 원래 들어있던 '4'를 pop 한다.

 

→ 결과적으로 '4'가 pop 되었다.

 

입력받은 원소 '4'를 1번 자료구조인 큐에 push 한 뒤, 원래 들어있던 '2'를 pop 한다.

pop 된 '2'를 바로 다음 자료구조인 2번 자료구조 스택에 push 하고, 다시 pop 한다.

pop 된 '2'를 바로 다음 자료구조인 3번 자료구조 스택에 push 하고, 다시 pop 한다.

pop 된 '2'를 바로 다음 자료구조인 4번 자료구조 큐에 push 하고, 원래 들어있던 '1'를 pop 한다.

 

→ 결과적으로 '1'이 pop 되었다.

 

입력받은 원소 '7'을 1번 자료구조인 큐에 push 한 뒤, 원래 들어있던 '4'를 pop 한다.

pop 된 '4'를 바로 다음 자료구조인 2번 자료구조 스택에 push 하고, 다시 pop 한다.

pop 된 '4'를 바로 다음 자료구조인 3번 자료구조 스택에 push 하고, 다시 pop 한다.

pop 된 '4'를 바로 다음 자료구조인 4번 자료구조 큐에 push 하고, 원래 들어있던 '2'를 pop 한다.

 

→ 결과적으로 '2'이 pop 되었다.

 

▶ 전체 return 값은 '4 1 2'이다.

 

 

위 그림을 통해 알 수 있었던 점은 다음과 같다.

1. 스택은 아무 영향도 끼치지 않는다.
2. 초기 상태에 큐에 들어가 있던 값들(1, 4)이 역순으로 출력된 후 새롭게 입력받은 값을 출력하는데, 이때 수열의 길이 M만큼 리턴된다.

 

 

코드 전문

#include <stdio.h>

int main() {
    int n, m; // 자료구조의 개수, 삽입할 수열의 길이
    scanf("%d", &n);
    int a[100000]; // 수열 A, 자료구조의 종류(큐 or 스택)
    int b[100000]; // 수열 B, 각 자료구조에 들어있는 원소
    int queue[2000000];
    int index = 0;
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }
    
    for (int i = n - 1; i >= 0; --i) {
        if (a[i] == 0) {
            queue[index++] = b[i];
        }
    }
    
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int x;
        scanf("%d", &x);
        queue[index++] = x;
        printf("%d ", queue[i]);
    }
    return 0;
}

 

자료구조의 종류(큐 혹은 스택)를 식별하는 값을 a 배열에 입력받는다.

각 자료구조에 들어있는 원소들을 b 배열에 입력받는다.

큐에 있는 값들만 역순으로 queue 배열에 넣어준다.

삽입할 수열의 길이 m을 입력받은 뒤, m만큼 반복하면서 새로운 값을 queue 배열에 저장하고, 동시에 queue 배열을 앞에서부터 차례로 출력한다. 이렇게 하면 queue 배열에는 큐에 들어있는 초기 원소 + 새로 입력받은 원소가 들어가게 되고, 앞에서부터 m번째 수까지만 잘라 출력하게 된다.

 

예를 들어,
초기에 큐에 들어있는 원소: 1, 4
새로 입력받은 원소: 2, 4, 7

queue[0] = 4
queue[1] = 1
queue[2] = 2
queue[3] = 4
queue[4] = 7

m = 3이므로 queue[2]까지만 출력하여 [4, 1, 2] 출력

 

 

* 배열 크기로 인해 런타임 에러가 계속 떴다... 배열을 충분히 큰 크기로 만들어줘야 한다!

 

 

정답!!

 

 

---

 

끝