[백준 #10845] 큐
https://www.acmicpc.net/problem/10845
문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
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
해결 코드
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
public class Baekjoon10845 {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
Queue<String> queue = new LinkedList<>();
StringBuilder sb = new StringBuilder();
for(int i=0; i<n; i++) {
String input = scanner.next();
if(input.equals("push")) {
queue.add(scanner.next());
}
else if (input.equals("pop")) {
if(queue.isEmpty()) sb.append("-1\n");
else sb.append(queue.remove() + "\n");
}
else if (input.equals("size")) {
sb.append(queue.size() + "\n");
}
else if (input.equals("empty")) {
if(queue.isEmpty()) sb.append("1\n");
else sb.append("0\n");
}
else if (input.equals("front")) {
if(queue.isEmpty()) sb.append("-1\n");
else sb.append(queue.peek() + "\n");
}
else if (input.equals("back")) {
if(queue.isEmpty()) sb.append("-1\n");
else {
Queue<String> tempQueue = new LinkedList<>();
while(queue.size() != 1) {
tempQueue.add(queue.remove());
}
sb.append(queue.peek() + "\n");
tempQueue.add(queue.remove());
queue = tempQueue;
}
}
}
System.out.println(sb);
}
}
📌 핵심 자료구조: Queue
1. Queue란?
• FIFO (First In First Out) 구조: 먼저 들어간 데이터가 먼저 나온다.
• Java에서는 LinkedList로 Queue를 쉽게 구현할 수 있음.
Queue<String> queue = new LinkedList<>();
기본 연산:
| 연산 | 설명 |
| add() | 큐의 맨 뒤에 원소 추가 |
| remove() | 큐의 맨 앞 원소 제거 + 반환 |
| peek() | 큐의 맨 앞 원소 확인 (제거 X) |
| isEmpty() | 큐가 비었는지 확인 |
| size() | 큐에 몇 개 원소 있는지 확인 |
📌 알고리즘 동작 흐름
1. 명령어 입력 받기:
int n = scanner.nextInt();
• 명령어의 개수 n을 입력받고, 반복문을 통해 명령어들을 처리함.
2. 명령어 처리:
| 명령어 | 수행 동작 |
| push X | queue.add(X) → X를 큐의 뒤에 추가 |
| pop | 비었으면 -1, 아니면 queue.remove()로 맨 앞 원소 제거 |
| size | queue.size() 출력 |
| empty | 비었으면 1, 아니면 0 |
| front | 비었으면 -1, 아니면 queue.peek() |
| back | 비었으면 -1, 아니면 큐 끝의 원소 출력 |
📌 주목할 부분: back 처리
문제는 Queue 인터페이스 자체에는 “맨 뒤 원소를 보는 기능이 없다”는 점.
그래서 큐를 임시 큐로 하나씩 빼면서 마지막 원소를 찾고, 다시 원래 큐로 복원하는 방식으로 구현했음.
Queue<String> tempQueue = new LinkedList<>();
while(queue.size() != 1) {
tempQueue.add(queue.remove());
}
sb.append(queue.peek() + "\n");
tempQueue.add(queue.remove());
queue = tempQueue;
✅ 시간 복잡도 분석
• push, pop, size, empty, front → O(1)
• back → O(N)
• 큐의 모든 원소를 하나씩 빼고 다시 넣기 때문에 N개의 원소에 대해 O(N)
📌 개선할 수 있는 점:
Queue의 끝 원소 추적
• back 처리 시 매번 O(N) 시간 소모 → 비효율적
• 해결 방법:
• 큐에 원소를 추가(push)할 때마다, 마지막 원소 값을 별도로 변수에 저장해두면 됨.
String last = "";
if (input.equals("push")) {
String x = scanner.next();
queue.add(x);
last = x; // 마지막 원소 기억
}
else if (input.equals("back")) {
if(queue.isEmpty()) sb.append("-1\n");
else sb.append(last + "\n"); // 바로 출력
}
문자열 + 연산이 아닌 sb.append() 이용하기
sb.append(queue.remove() + "\n")이 아닌 sb.append(queue.remove).append("\n"); 으로 StringBuilder 활용
📌 정리
| 자료구조 | 사용 이유 | 특징 |
| Queue | FIFO 특성을 활용해 명령어 순서대로 처리 | LinkedList 기반 |
| StringBuilder | 출력 최적화 (여러 번 출력 → 한 번에 출력) | I/O 시간 단축 |
| 임시 큐 사용 (back 처리) | 맨 뒤 원소 확인을 위해 | O(N), 비효율적 (개선 가능) |
📌 전체 시간 복잡도
• 총 명령어 N개
• 대부분 O(1), 하지만 기존 코드의 back이 O(N) → 최악 시 O(N^2)
• 개선하면 전체 시간 복잡도는 O(N)
Queue의 기본 연산으로 처리할 수 없는 건 변수 하나 더 써서 해결할 수 있다!