Java 백준 24511 queuestack

백준 링크

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

24511번: queuestack

---

문제

입력

출력

입출력 예시

---

제출한 코드

import java.io.*;
import java.util.*;

class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		int N = Integer.parseInt(br.readLine());
		int[] type = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			type[i] = Integer.parseInt(st.nextToken());

		}
		st = new StringTokenizer(br.readLine());
		Deque<Integer> test = new ArrayDeque();
		for (int i = 0; i < N; i++) {
			int inputData = Integer.parseInt(st.nextToken());
			if (type[i] == 0) {
				test.addFirst(inputData);
			}
		}

		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			test.addLast(Integer.parseInt(st.nextToken()));
		}
		for (int i = 0; i < M; i++) {

			sb.append(test.pollFirst()).append(" ");
		}
		System.out.println(sb);
	}
}

 

입력 조건을 보면 들어오는 데이터의 크기가 최대 1,000,000,000이고 시간 제한이 1초라 적용된 조건이 굉장히 빡빡한 문제이다.

기본적으로 Stack과 Queue를 같이 편하게 사용하기 위해서 Deque를 이용했다.

Stack인 위치에 들어오는 데이터는 계속해서 이동하게 되고 Queue인 위치에 들어오는 데이터는 기존 데이터 빠져나오게된다.

해당 로직을 인지하고 코드를 작성한다.

 

1. 빡빡한 시간 제한을 인지하고 최소한의 시간복잡도를 만들어 낸다.

2. stack에 들어오는 data는 고려할 필요가 없기에 data를 입력받으면서 queue인 경우만 따로 deque내부 맨 앞에 저장해준다.

3. 새롭게 들어오는 수열에 대한 정보는 deque의 뒤에 순차적으로 추가해준다.

4. 입력된 수열의 수 만큼 deque의 앞에서부터 순서대로 출력해준다.