백준 풀기

백준 10845번: 큐 with Java

삼겹살파튀 2025. 4. 19. 17:44

큐

 
 
시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 (추가 시간 없음) 256 MB 151954 72554 57027 49.431%

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

  • push X: 정수 X를 큐에 넣는 연산이다.
  • pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 큐에 들어있는 정수의 개수를 출력한다.
  • empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
  • front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1 복사

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

예제 출력 1 복사

1
2
2
0
1
2
-1
0
1
-1
0
3

 

 

 

 

스택을 풀었으니까 큐를 풀어보기로 했다.

큐...

큐......

흠냐

 

큐에 대한 기억은 FIFO뿐...

큐 기억 안 나서 지피티한테 물어봤다.

 

🔄 큐의 기본 개념

  • 선입선출(FIFO: First In, First Out) 방식입니다.
    • 먼저 들어간 데이터가 먼저 나옵니다.
    • 마치 줄 서는 것과 같아요. 먼저 줄 선 사람이 먼저 처리되는 거죠.

🧱 큐의 주요 동작

  1. enqueue: 큐의 뒤쪽(Rear)에 데이터를 추가
  2. dequeue: 큐의 앞쪽(Front)에서 데이터를 제거
  3. peek / front: 큐의 맨 앞에 있는 데이터를 확인만 함 (제거하지 않음)
  4. isEmpty: 큐가 비어 있는지 확인

📦 큐를 사용하는 예

  • 프린터 작업 순서
  • 콜센터 고객 대기
  • BFS(너비 우선 탐색) 알고리즘
  • CPU 태스크 스케줄링

 

그렇구만. 근데 물어보기 전이랑 후의 내 머리 차이가 별로 나지 않는다... 걍 선입선출밖에 읍잖어!!!!

 

예시 코드 LinkedList 주길래 LinkedList도 줄줄이 소세지처럼 엮여있던 것밖에 생각 안 나서 또 한 번 물어봄.

 

 

 

LinkedList는 자바에서 연결 리스트를 구현한 클래스예요. 연결 리스트는 각 요소가 다음 요소를 가리키는 방식으로 데이터를 저장하는 자료구조입니다. 배열과 달리, 데이터를 저장하는 위치가 연속적이지 않고 각 요소가 독립적으로 존재하면서 포인터(또는 참조)로 서로 연결돼 있어요.

자바에서는 java.util.LinkedList 클래스가 이를 구현하고 있으며, List, Queue, Deque 인터페이스를 구현하고 있어서, 다양한 방식으로 활용할 수 있어요.

🔸 LinkedList의 구조

연결 리스트의 기본 개념은 각각의 요소가 데이터와 포인터(다음 요소를 가리키는)를 가지고 있다는 점이에요. 연결 리스트는 크게 **단일 연결 리스트(Singly Linked List)**와 **이중 연결 리스트(Doubly Linked List)**로 나뉘는데, 자바의 LinkedList는 이중 연결 리스트입니다.

이중 연결 리스트는 각 노드가 두 개의 포인터를 가지며:

  • 앞쪽(previous) 포인터는 이전 노드를 가리키고,
  • 뒤쪽(next) 포인터는 다음 노드를 가리킵니다.

🔸 LinkedList의 장점

  1. 동적 크기 조정: 배열은 크기가 고정되어 있지만, 연결 리스트는 크기가 동적으로 변경될 수 있어요. 요소를 추가하거나 제거할 때 크기를 조정하는 데 시간이 걸리지 않아요.
  2. 삽입 및 삭제 효율적: 배열과 달리 삽입이나 삭제가 효율적이에요. 중간에 요소를 추가하거나 제거할 때, 다른 요소들을 이동시킬 필요 없이, 포인터만 수정하면 되니까요.
  3. 메모리 절약: 배열처럼 미리 메모리를 할당할 필요가 없기 때문에 메모리를 절약할 수 있어요.

🔸 LinkedList의 단점

  1. 임의 접근 불가: 배열처럼 인덱스로 바로 접근할 수 없어요. 데이터에 접근하려면 처음부터 끝까지 순차적으로 접근해야 해서 검색에 시간이 걸릴 수 있어요.
  2. 추가적인 메모리 사용: 각 노드는 데이터 + 두 개의 포인터(이전 노드와 다음 노드)를 가지고 있어 메모리 사용이 비교적 큽니다.

 

Queue 인터페이스 메서드

  • add(E e): 큐의 맨 뒤에 요소를 추가합니다. 큐가 꽉 차있다면 IllegalStateException이 발생합니다.
  • offer(E e): 큐의 맨 뒤에 요소를 추가합니다. 큐가 꽉 차면 false를 반환하고 예외는 발생하지 않습니다.
  • remove(): 큐의 맨 앞에서 요소를 제거하고 반환합니다. 큐가 비어있다면 NoSuchElementException이 발생합니다.
  • poll(): 큐의 맨 앞에서 요소를 제거하고 반환합니다. 큐가 비어있으면 null을 반환합니다.
  • element(): 큐의 맨 앞에 있는 요소를 반환합니다. 큐가 비어있으면 NoSuchElementException이 발생합니다.
  • peek(): 큐의 맨 앞에 있는 요소를 반환합니다. 큐가 비어있으면 null을 반환합니다.
  • size(): 큐에 저장된 요소의 개수를 반환합니다.
  • isEmpty(): 큐가 비어있는지 여부를 확인합니다. 비어있으면 true, 아니면 false를 반환합니다.

 

아 근데 뭔가 다 내가 어렴풋이 알고 있던 거야....

일단 메서드 다 주워왔으니까

일단 코드 짜보겟습니다.

 

스택 코드 베껴와서 수정했는데 맨 뒤 요소는... 이거 어케 가져와야하지 계속계속 뒤로 가기? ㅎㅎㅎ

 

...

죄송합니다! 검색했습니다!

LinkedList의 peekLast() 메서드 사용하면 맨 뒤에 거 볼 수 있다고 합니다!

 

그렇게 나온

누더기 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Queue<Integer> queue = new LinkedList<>();
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            switch (input) {
                case "pop":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(queue.poll());
                    break;
                case "size":
                   System.out.println(queue.size());
                   break;
                case "empty":
                    if (queue.isEmpty()) {
                        System.out.println(1);
                        break;
                    }
                    System.out.println(0);
                    break;
                case "front":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(queue.peek());
                    break;
                case "back":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(queue.peekLast());
                default:
                    int num = Integer.parseInt(input.split(" ")[1]);
                    queue.offer(num);
            }
        }
    }
}

 

 

 

...

므ㅝ야!!!!!!!!!!!

 

back case에 break 안 걸어서 그런가??

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Queue<Integer> queue = new LinkedList<>();
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            switch (input) {
                case "pop":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(queue.poll());
                    break;
                case "size":
                   System.out.println(queue.size());
                   break;
                case "empty":
                    if (queue.isEmpty()) {
                        System.out.println(1);
                        break;
                    }
                    System.out.println(0);
                    break;
                case "front":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(queue.peek());
                    break;
                case "back":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(queue.peekLast());
                    break;
                default:
                    int num = Integer.parseInt(input.split(" ")[1]);
                    queue.offer(num);
            }
        }
    }
}

 

 

검색 결과 저걸 쓰려면 덱으로 변환해야 한단다...

근데 그건 뭔가 문제랑 안 맞지 않나??

 

그냥 마지막 요소를 저장할 int 변수 lastNum을 사용해서 새로운 요소 더할 때마다 갱신해주기로 했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Queue<Integer> queue = new LinkedList<>();
        int lastNum = 0;
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            switch (input) {
                case "pop":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(queue.poll());
                    break;
                case "size":
                   System.out.println(queue.size());
                   break;
                case "empty":
                    if (queue.isEmpty()) {
                        System.out.println(1);
                        break;
                    }
                    System.out.println(0);
                    break;
                case "front":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(queue.peek());
                    break;
                case "back":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(lastNum);
                    break;
                default:
                    int num = Integer.parseInt(input.split(" ")[1]);
                    queue.offer(num);
                    lastNum = num;
            }
        }
    }
}

 

 

 

구웃

다음은 덱이다!!

덱도 이거 변형해서 써야지 ㅎㅎ

 

 

+

찝찝했던 default 코드 수정

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Queue<Integer> queue = new LinkedList<>();
        int lastNum = 0;
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            switch (input[0]) {
                case "push":
                    int num = Integer.parseInt(input[1]);
                    queue.offer(num);
                    lastNum = num;
                    break;
                case "pop":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(queue.poll());
                    break;
                case "size":
                   System.out.println(queue.size());
                   break;
                case "empty":
                    if (queue.isEmpty()) {
                        System.out.println(1);
                        break;
                    }
                    System.out.println(0);
                    break;
                case "front":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(queue.peek());
                    break;
                case "back":
                    if (queue.isEmpty()) {
                        System.out.println(-1);
                        break;
                    }
                    System.out.println(lastNum);
                    break;
            }
        }
    }
}

'백준 풀기' 카테고리의 다른 글

백준 11866번: 요세푸스 문제 0 with Java  (0) 2025.04.20
백준 10866번: 덱 with Java  (0) 2025.04.20
백준 10828번: 스택 with Java  (0) 2025.04.18
백준 17087번: 숨바꼭질 6 with Java  (1) 2025.04.17
백준 4963번: 섬의 개수 with Java  (0) 2024.08.25

'백준 풀기'의 다른글

  • 현재글백준 10845번: 큐 with Java

관련글

티스토리툴바