[Silver III] queuestack - 24511
성능 요약
메모리: 88944 KB, 시간: 600 ms
분류
자료 구조, 덱, 큐, 스택
제출 일자
2023년 11월 23일 09:09:58
문제 설명
한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 queuestack이다.
queuestack의 구조는 다음과 같다. 1
번, 2 번, ... , N 번의 자료구조(queue 혹은 stack)가 나열되어있으며, 각각의 자료구조에는 한 개의 원소가 들어있다.queuestack의 작동은 다음과 같다.
- x0을 입력받는다.
- x0을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x1이라 한다.
- x1을 2번 자료구조에 삽입한 뒤 2번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x2이라 한다.
- ...
- xN−1을 N번 자료구조에 삽입한 뒤 N번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 xN이라 한다.
- xN을 리턴한다.
도현이는 길이 M의 수열 C를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 1 참고)
queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.
입력
첫째 줄에 queuestack을 구성하는 자료구조의 개수 N
이 주어진다. (1≤N≤100000 )둘째 줄에 길이 N의 수열 A가 주어진다. i번 자료구조가 큐라면 Ai=0, 스택이라면 Ai=1이다.
셋째 줄에 길이 N의 수열 B가 주어진다. Bi는 i번 자료구조에 들어 있는 원소이다. (1≤Bi≤1000000000)
넷째 줄에 삽입할 수열의 길이 M이 주어진다. (1≤M≤100000)
다섯째 줄에 queuestack에 삽입할 원소를 담고 있는 길이 M
의 수열 C 가 주어진다. (1≤Ci≤1000000000)입력으로 주어지는 모든 수는 정수이다.
출력
수열 C의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.
1. 스택은 LIFO 구조로 방금 들어간 값이 방금 나온다 그러므로 스택은 큐 스택에서 신경쓰지 않아도 됨
2. 큐만 있다는 가정하에 원소를 추가하고 마지막 원소가 나오는 FIFO구조이다.
3. DEQUQ로 선언하면 편리하게 구현이 가능함
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Deque<Integer> queue = new ArrayDeque<>();
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[n];
for(int i = 0; i < n;i++){
arr[i] = Integer.valueOf(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++){
int tmp = Integer.parseInt(st.nextToken());
if(arr[i] == 0){
queue.offer(tmp);
}
}
int m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < m; i++){
int tmp = Integer.parseInt(st.nextToken());
queue.offerFirst(tmp);
sb.append(queue.pollLast() + " ");
}
System.out.println(sb.toString());
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 11652번 : 카드 Silver4(실버4) - JAVA[자바] (0) | 2023.11.24 |
---|---|
[백준] 11722번 : 가장 긴 감소하는 부분 수열 Silver2(실버2) - JAVA[자바] (0) | 2023.11.24 |
[백준] 2346번 : 풍선 터뜨리기 Silver3(실버3) - JAVA[자바] (1) | 2023.11.23 |
[백준] 28279번 : 덱2 Silver 4(실버4) - JAVA[자바] (0) | 2023.11.23 |
[백준] 12789번 : 도키도키 간식드리미 Silver3(실버3) - JAVA[자바] (1) | 2023.11.22 |