[BOJ/백준] 24511번. queuestack - Java[자바]

문제

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

24511번: queuestack

 

 

잘못 접근하기 좋은 풀이

문제에 나와있는 그대로 모든 원소를 삽입, pop을 해보겠다

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Queue<Integer> queue = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0) {
                queue.add(Integer.parseInt(st.nextToken()));
            }
            else {
                stack.add(Integer.parseInt(st.nextToken()));
            }
        }
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int x;
        for (int i = 0; i < m; i++) {
            x = Integer.parseInt(st.nextToken());
            for (int j = 0; j < n; j++) {
                if (arr[j] == 0) {
                    queue.add(x);
                    x = queue.poll();
                }
            }
            bw.write(x + " ");
        }
        bw.flush();
        bw.close();
    }
}

 

시간 복잡도(시간 제한을 통과 하지 못한 풀이)

O(nm)으로 시간 제한 1초를 넘어버린다. 불필요한 연산이 포함되어 있다.

 

-----------------------------------------

접근

• 스택 자료구조의 경우 삽입된 값을 다시 pop을 하기 때문에, 스택의 연산에 대해 신경쓰지 않아도 된다.
  • 예제 입력 2처럼 스택으로만 이루어 진 경우 삽입한 값이 그대로 return 된다
• 따라서 queuestack 내에서 queue가 존재하는 경우 queue의 연산이 작동하는 것을 생각해보자

예제 입력 1을 예시로 봐보자. 큐에는 (후단) [4, 1] (전단) 가 있다.

 

• 2를 삽입하면
  • 큐 : (후단) [1, 2] (전단),  4가 리턴된다
• 4를 삽입하면
  • 큐 : (후단) [2, 4] (전단), 1이 리턴된다
• 7를 삽입하면
  • 큐 : (후단) [4, 7] (전단),  2가 리턴된다

 

즉, 후단에서 pop한 값이 리턴되고, 삽입하려는 값은 큐의 전단에 삽입된다. 이를 통해 덱(Deque) 자료구조를 이용해야 겠다는 생각을 해야한다. pollLast()를 통해 리턴되는 값을 찾아야 한다

 

삽입하려는 값을 덱에 삽입한 후 삽입한 횟수 만큼 pollLast()를 해도 문제를 통과할 수 있고, 큐의 크기와 삽입하려는 수열의 길이의 대소관계를 비교해서 경우에 따라 코드를 세분화해도 된다(세분화 하는 경우 코드가 조금 길어진다).

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Deque<Integer> queue = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        int temp;
        for (int i = 0; i < n; i++) {
            temp = Integer.parseInt(st.nextToken());
            if (arr[i] == 0) {
                queue.add(temp);
            }
        }
        int m = Integer.parseInt(br.readLine());
        int queueSize = queue.size();
        if (queueSize == 0) {
            System.out.print(br.readLine());
            return;
        }
        else if (m > queueSize) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < queueSize; i++) {
                bw.write(queue.pollLast() + " ");
            }
            for (int i = 0; i < m - queueSize; i++) {
                bw.write(st.nextToken() + " ");
            }
        }
        else if (m == queueSize) {
            for (int i = 0; i < queueSize; i++) {
                bw.write(queue.pollLast() + " ");
            }
        }
        else {
            for (int i = 0; i < m; i++) {
                bw.write(queue.pollLast() + " ");
            }
        }
        bw.flush();
        bw.close();
    }
}