[알고리즘/백준] 18258번 : 큐2

문제	18258번 : 큐2
문제링크	https://www.acmicpc.net/problem/18258
난이도	S4
언어	Java
분류	자료구조 | 자료구조, 큐

 

 

📌 최종 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력 - 명령의 수
        int n = Integer.parseInt(br.readLine());

        // 큐
        LinkedList<Integer> queue = new LinkedList<>();

        // 명령의 수 만큼 반복
        for(int i =0; i < n; i++){
            // 입력하는 명령어
            String[] inputs = br.readLine().split(" ");

            switch (inputs[0]) {
                case "push" :
                    int value = Integer.parseInt(inputs[1]);
                    queue.add(value);
                    break;
                case "pop" :
                    if(queue.isEmpty()){
                        // 비어있을 경우
                        bw.write("-1" + "\n");
                    } else {
                        bw.write(queue.poll() + "\n");
                    }
                    break;
                case "size" :
                    bw.write(queue.size() + "\n");
                    break;
                case "empty" :
                    if(queue.isEmpty()){
                        // 비어있을 경우
                        bw.write("1" + "\n");
                    } else {
                        bw.write("0" + "\n");
                    }
                    break;
                case "front" :
                    if(queue.isEmpty()){
                        // 비어있을 경우
                        bw.write("-1" + "\n");
                    } else {
                        bw.write(queue.peek() + "\n");
                    }
                    break;
                case "back" :
                    if(queue.isEmpty()){
                        // 비어있을 경우
                        bw.write("-1" + "\n");
                    } else {
                        bw.write(queue.get(queue.size()-1)+ "\n");
                    }
                    break;
            }

        }

        bw.flush();
        bw.close();
    }
}

📌 구해야 하는 정답

명령어에 대한 결과

• push X: 큐에 x 넣기
• pop: 큐의 가장 앞의 정수를 빼서 출력, 없을 경우 -1 출력
• size: 큐에 있는 정수의 개수를 출력
• empty: 큐가 비어있으면 1, 아니면 0을 출력
• front: 큐의 가장 앞에 있는 정수를 출력, 없을 경우 -1 출력
• back: 큐의 가장 뒤에 있는 정수를 출력, 없을 경우 -1 출력

📌 풀이하기

1. 입력받기

// 입력 - 명령의 수
int n = Integer.parseInt(br.readLine());

// 입력하는 명령어 종류
String[] inputs = br.readLine().split(" ");

 

2. 큐 계산 & 결과 출력

for(int i =0; i < n; i++){
    // 입력하는 명령어
    String[] inputs = br.readLine().split(" ");

    switch (inputs[0]) {
        case "push" :
            int value = Integer.parseInt(inputs[1]);
            queue.add(value);
            break;
        case "pop" :
            if(queue.isEmpty()){
                // 비어있을 경우
                bw.write("-1" + "\n");
            } else {
                bw.write(queue.poll() + "\n");
            }
            break;
        case "size" :
            bw.write(queue.size() + "\n");
            break;
        case "empty" :
            if(queue.isEmpty()){
                // 비어있을 경우
                bw.write("1" + "\n");
            } else {
                bw.write("0" + "\n");
            }
            break;
        case "front" :
            if(queue.isEmpty()){
                // 비어있을 경우
                bw.write("-1" + "\n");
            } else {
                bw.write(queue.peek() + "\n");
            }
            break;
        case "back" :
            if(queue.isEmpty()){
                // 비어있을 경우
                bw.write("-1" + "\n");
            } else {
                bw.write(queue.get(queue.size()-1)+ "\n");
            }
            break;
    }
}

 

초반에는 다음처럼 ArrayList를 이용하여 풀이하였는데 메모리 초과로 LinkedList 방식으로 변경하여 풀이하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력 - 명령의 수
        int n = Integer.parseInt(br.readLine());

        // 큐
        ArrayList<Integer> queue = new ArrayList<Integer>(n);

        // 명령의 수 만큼 반복
        for(int i =0; i < n; i++){
            // 입력하는 명령어
            String[] inputs = br.readLine().split(" ");

            switch (inputs[0]) {
                case "push" :
                    int value = Integer.parseInt(inputs[1]);
                    queue.add(value);
                    break;
                case "pop" :
                    if(queue.isEmpty()){
                        // 비어있을 경우
                        bw.write("-1" + "\n");
                    } else {
                        bw.write(queue.get(0) + "\n");
                        queue.remove(0);
                        for(int j = 0; j < queue.size()-1; j ++){
                            queue.add(j, queue.get(j+1));
                        }
                    }
                    break;
                case "size" :
                    bw.write(queue.size() + "\n");
                    break;
                case "empty" :
                    if(queue.isEmpty()){
                        // 비어있을 경우
                        bw.write("1" + "\n");
                    } else {
                        bw.write("0" + "\n");
                    }
                    break;
                case "front" :
                    if(queue.isEmpty()){
                        // 비어있을 경우
                        bw.write("-1" + "\n");
                    } else {
                        bw.write(queue.get(0) + "\n");
                    }
                    break;
                case "back" :
                    if(queue.isEmpty()){
                        // 비어있을 경우
                        bw.write("-1" + "\n");
                    } else {
                        bw.write(queue.get(queue.size() -1) + "\n");
                    }
                    break;
            }

        }

        bw.flush();
        bw.close();
    }
}

 

LinkedList는 처음 사용하여 메서드를 검색하여 풀었다.

 

pop할 때 .poll()를 하면 가장 앞의 수가 빠지면서 출력되는 게 신기했다.

가장 앞의 수를 출력만 할 때는 get(0)을 해도 되고, peek()를 해도 된다.

 

📌 코드 설계하기

1. 명령어의 개수를 입력 받습니다.
2. 큐를 위한 변수를 선언합니다.
3. 명령어를 공백을 기준으로 parsing 합니다.
4. push 명령어 구현
5. pop 명령어 구현
6. size 명령어 구현
7. empty 명령어 구현
8. front 명령어 구현
9. back 명령어 구현

 

📌 시간 복잡도

각 명령어의 시간복잡도는 각 항목에서 확인하실 수 있습니다.

추가로 큐 자료구조의 대표적인 연산들의 시간복잡도는 아래와 같습니다.