반응형
이번 글에서는 백준 28278번 문제를 통해
스택(자료구조)를 구현하고 활용해 보자.
문제 핵심
- N : 명령의 수 ( 1 <= N <= 1,000,000 )
- 명령 1 ~ 5 까지 주어진다.
- 1. Push
- 2. Pop
- 3. Size
- 4. IsEmpty
- 5. Peek
- 명령은 하나씩 주어진다.
풀이 과정
다음 문제는 스택을 구현하고 처리하는 과정이라고 할 수 있다.
1. 함수 구현하기
1 ~ 5의 명령어와 같이 스택에 필요한 함수들을 구현하자.
private static int isEmpty() {
if (list.isEmpty()) {
return 1;
}
return 0;
}
private static Integer peek() {
if (list.isEmpty()) {
return -1;
}
return list.getFirst();
}
private static Integer pop() {
if (list.isEmpty()) {
return -1;
}
return list.removeFirst();
}
private static void push(int num) {
list.addFirst(num);
}
문제에 맞게 명령어들을 변형하여 함수를 구현하였다.
2. 구현한 함수 활용하기 ( Main 작성 )
- 문제를 다음과 같이 풀었지만, 1 ~ 5의 단순한 숫자나 문자열로 처리할 경우 Switch문이 더 적합하며 범위 계산이나 null 값 계산 등이 아니라면 Switch문으로 처리하는 것이 좋아 보인다.
- List 는 JAVA의 LinkedList<> 클래스를 활용하였다.
- ArrayList or List를 활용해서 사용할 수 있기도 하지만, 미리 만들어두는 구조보다는 문제제목과 같은 자료구조에 맞춰서 사용하였다.
private static final LinkedList<Integer> list = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder stringBuilder = new StringBuilder();
int num = Integer.parseInt(bufferedReader.readLine());
StringTokenizer stringTokenizer;
String command;
for (int i = 0; i < num; i++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
command = stringTokenizer.nextToken();
if (command.equals("1")) {
push(Integer.parseInt(stringTokenizer.nextToken()));
} else if (command.equals("2")) {
stringBuilder.append(pop())
.append("\n");
} else if (command.equals("3")) {
stringBuilder.append(list.size())
.append("\n");
} else if (command.equals("4")) {
stringBuilder.append(isEmpty())
.append("\n");
} else if (command.equals("5")) {
stringBuilder.append(peek())
.append("\n");
}
}
System.out.println(stringBuilder);
}
스택 ( 자료구조 ) - JAVA
오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.접시를 쌓아올린다고 생각하면 된다.스택 ( Stack )후
p-coding.tistory.com
백준에서는 여러 프로그래밍 언어 중 Java가 비교적 느린 편이기 때문에, 많은 사람이 속도 최적화에 집중하거나 단순히 문제를 해결하는 데만 초점을 맞춰 코드를 작성하는 경우가 많다. (물론 브론즈 ~ 실버 수준의 문제에서는 속도 차이가 크게 중요하지 않다.)
하지만 이러한 문제의 핵심은 스택을 직접 구현하고 이해하는 것에 있다.
예를 들어, 명령어가 4일 때 list.isEmpty() ? 1 : 0을 사용하면 간편하게 해결할 수 있다.
그러나 이는 LinkedList 클래스의 isEmpty() 메서드를 활용한 것이지,
우리가 구현해야 할 스택의 isEmpty()가 아니다.
비록 같은 기능을 수행하지만, 개념적으로 다른 의미를 가진다.
즉,
문제를 통과하는 것에만 집중하기보다는, 정확한 개념을 이해하고 접근하는 것이 더 중요하다.
전체 코드
물론 다음 코드도 완벽하지는 않다.
package org.example;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
private static final LinkedList<Integer> list = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder stringBuilder = new StringBuilder();
int num = Integer.parseInt(bufferedReader.readLine());
StringTokenizer stringTokenizer;
String command;
for (int i = 0; i < num; i++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
command = stringTokenizer.nextToken();
if (command.equals("1")) {
push(Integer.parseInt(stringTokenizer.nextToken()));
} else if (command.equals("2")) {
stringBuilder.append(pop())
.append("\n");
} else if (command.equals("3")) {
stringBuilder.append(list.size())
.append("\n");
} else if (command.equals("4")) {
stringBuilder.append(isEmpty())
.append("\n");
} else if (command.equals("5")) {
stringBuilder.append(peek())
.append("\n");
}
}
System.out.println(stringBuilder);
}
private static int isEmpty() {
if (list.isEmpty()) {
return 1;
}
return 0;
}
private static Integer peek() {
if (list.isEmpty()) {
return -1;
}
return list.getFirst();
}
private static Integer pop() {
if (list.isEmpty()) {
return -1;
}
return list.removeFirst();
}
private static void push(int num) {
list.addFirst(num);
}
}반응형
'백준 단계별 풀이' 카테고리의 다른 글
| [ 백준 11866번 문제 ] 요세푸스 문제 0 (2) | 2025.03.01 |
|---|---|
| [ 백준 2164번 문제 ] 카드2 (0) | 2025.02.27 |
| [ 백준 17103번 문제 ] 골드바흐 파티션 - JAVA (0) | 2025.01.04 |
| [ 백준 28116번 문제 ] 선택 정렬의 이동 거리 (2) | 2024.12.27 |
| [ 백준 23881번 문제 ] 알고리즘 수업 - 선택 정렬 1 (0) | 2024.12.17 |
