백준 28278번: 스택 2
정수를 저장하는 스택을 구현하고, 5가지 종류의 명령에 따라 결과를 출력하는 문제입니다. 자료구조의 가장 기본인 스택(Stack)의 LIFO(Last-In, First-Out) 특성을 이해하고, Java에서 스택을 구현할 때 권장되는 ArrayDeque를 활용하는 것이 핵심입니다.
✅ 문제 개요
| 항목 | 내용 |
|---|---|
| 문제 번호 | 28278번 - 스택 2 |
| 난이도 | 실버 4 |
| 핵심 알고리즘 | 자료구조, 스택, ArrayDeque |
✅ 문제 설명 요약
- 입력:
- 첫째 줄: 명령의 수
N(1 ≤ N ≤ 1,000,000) - 이후
N개의 줄: 1부터 5까지의 정수로 시작하는 명령이 주어짐
- 첫째 줄: 명령의 수
- 출력: 2, 3, 4, 5번 명령에 대한 결과를 한 줄에 하나씩 출력
- 명령 규칙:
1 X: 정수 X를 스택에 넣는다.2: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력. 없으면 -1 출력.3: 스택에 들어있는 정수의 개수를 출력.4: 스택이 비어있으면 1, 아니면 0을 출력.5: 스택의 가장 위에 있는 정수를 출력. 없으면 -1 출력.
✅ 풀이 전략
이 문제는 스택의 5가지 기본 연산을 구현하는 문제입니다. Java에서 스택을 구현할 때는 전통적인 Stack 클래스보다 성능이 우수하고 LIFO/FIFO를 모두 지원하는 ArrayDeque를 사용하는 것이 현대적인 프로그래밍에서 권장됩니다.
1️⃣ 핵심 자료구조: ArrayDeque로 스택 구현
ArrayDeque는Deque(Double-Ended Queue) 인터페이스의 구현체로, 양쪽 끝에서 데이터를 추가/삭제할 수 있어 스택(LIFO)과 큐(FIFO)의 기능을 모두 수행할 수 있습니다.- 스택으로 사용할 때는 한쪽 끝(예: 마지막)에서만 데이터를 추가하고(
push) 제거(pop)합니다. Stack클래스와 달리 동기화(synchronization) 오버헤드가 없어 단일 스레드 환경에서 더 빠릅니다.
2️⃣ ArrayDeque와 명령어 매핑
ArrayDeque가 제공하는Deque인터페이스의 메소드들은 스택의 모든 기능을 완벽하게 지원합니다.
| 명령어 | 동작 | java.util.ArrayDeque 메소드 | 비어있을 때 처리 |
|---|---|---|---|
1 X | X를 스택에 넣음 | stack.push(X) | - |
2 | 맨 위 정수를 빼고 출력 | stack.pop() | -1 출력 |
3 | 스택의 크기 출력 | stack.size() | 0 출력 |
4 | 스택이 비었는지 확인 | stack.isEmpty() | 1 출력 |
5 | 맨 위 정수를 확인만 함 | stack.peek() | -1 출력 |
3️⃣ 알고리즘 설계
Deque<Integer> stack = new ArrayDeque<>();와 같이ArrayDeque객체를 생성합니다.- 명령의 수
N을 입력받고,N번 반복하는for문을 실행합니다. switch문을 사용하여 입력된 명령어(1~5)에 따라 로직을 분기합니다.- 각
case에서 해당하는ArrayDeque의 스택 관련 메소드를 호출합니다. - 특히 명령어 2와 5의 경우, 스택이 비어있는지(
stack.isEmpty()) 먼저 확인하고, 비어있다면-1을, 아니라면pop()또는peek()의 결과를BufferedWriter에 작성합니다. - 모든 명령이 끝나면
BufferedWriter의 내용을 출력(flush)합니다.
✅ Java 코드 예제
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayDeque;
import java.util.Deque;
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());
// 스택으로 사용할 Deque 선언
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int command = Integer.parseInt(st.nextToken());
switch (command) {
case 1:
int X = Integer.parseInt(st.nextToken());
stack.push(X);
break;
case 2:
if (stack.isEmpty()) {
bw.write("-1\n");
} else {
bw.write(stack.pop() + "\n");
}
break;
case 3:
bw.write(stack.size() + "\n");
break;
case 4:
if (stack.isEmpty()) {
bw.write("1\n");
} else {
bw.write("0\n");
}
break;
case 5:
if (stack.isEmpty()) {
bw.write("-1\n");
} else {
bw.write(stack.peek() + "\n");
}
break;
}
}
bw.flush();
bw.close();
br.close();
}
}⚠️ 실전 주의사항
| 항목 | 설명 |
|---|---|
| 입출력 성능 | N이 100만으로 매우 크므로, Scanner와 System.out.println을 반복 사용하면 시간 초과가 발생합니다. BufferedReader와 BufferedWriter 사용이 필수적입니다. |
| 빈 스택 예외 처리 | 스택이 비어있을 때 pop()이나 peek()을 호출하면 NoSuchElementException 런타임 에러가 발생합니다. 따라서 이들을 호출하기 전에는 반드시 isEmpty()로 비어있는지 확인하는 습관이 중요합니다. |
ArrayDeque 사용 권장 | Java 공식 문서에서도 스택 구현이 필요할 때 Stack 클래스보다 ArrayDeque를 사용하도록 권장하고 있습니다. 성능이 더 좋고 유연하기 때문입니다. |
| 명령어 파싱 | 명령어 1은 숫자 1과 정수 X 두 개를 입력받으므로, StringTokenizer를 사용하여 공백을 기준으로 분리해야 합니다. |
📝 마무리 요약
✔️ 스택의 LIFO 특성을 구현하는 문제이며, Java에서는 성능이 좋은 ArrayDeque를 사용하는 것이 권장됩니다.
✔️ ArrayDeque는 push, pop, peek, size, isEmpty 등 스택에 필요한 모든 메소드를 제공합니다.
✔️ 스택이 비어있을 때 pop이나 peek을 호출하면 예외가 발생하므로, isEmpty()로 사전 검사를 하는 것이 매우 중요합니다.
✔️ 많은 입출력을 처리해야 하므로 BufferedReader와 BufferedWriter를 사용하는 것이 시간 초과를 방지하는 열쇠입니다.
기록은 나의 무기, 원칙은 나의 방패