문제
https://www.acmicpc.net/problem/9935
풀이
스택에 저장되어 있는 데이터에 대한 인덱스 접근을 해야 하는 문제이다. 필자는 Stack에 get(인덱스) 연산이 되는 것을 이 문제를 풀면서 알게 되었다.
스택에서 인덱스 접근이 왜 될까? 그 이유는 Stack은 Vector 기반으로 되어 있어 존재한다.
풀이 방식은 간단하다.
1. 문자열에 있는 문자를 스택에 넣는다.
2. 폭발하는 문자열의 끝 문자와 스택의 peek() 맨 위의 문자가 같으면서, 폭발하는 문자열 길이 이상만큼 스택에 문자가 저장되어 있다면, 시작 인덱스를 구하고, 스택의 문자와 폭발하는 문자열을 비교해 문자열이 폭발할 수 있는지(flag) 기록한다.
3. 폭발하는 문자열이면 스택에서 폭발하는 문자열 길이만큼 뺀다.
소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
String bomb = br.readLine();
Stack<Character> stack = new Stack<>();
for(int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
//일단 스택에 넣어봄
stack.push(ch);
//스택의 제일 끝 문자와 폭발 문자열의 끝 문자가 같고, 스택의 폭탄 문자열보다 더 많이 들어가 있다면,
if (stack.peek() == bomb.charAt(bomb.length() - 1) && stack.size() >= bomb.length()) {
//폭발 문자열 여부
boolean flag = true;
//stack에서의 시작 인덱스
int startIdx = stack.size() - bomb.length();
//폭발 문자열 크기 만큼 비교,
for (int j = 0; j < bomb.length(); j++) {
if (bomb.charAt(j) != stack.get(j + startIdx)) {
flag = false;
break;
}
}
//폭발 문자열이라면, 폭발 문자열의 크기 만큼 뺀다.
if (flag) {
int length = bomb.length();
while (length > 0) {
stack.pop();
length -= 1;
}
}
}
}
//스택이 비어 있다면,
if (stack.isEmpty()) {
System.out.print("FRULA");
return;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
System.out.print(sb.reverse());
br.close();
}
}'Problem Solving > Baekjoon' 카테고리의 다른 글
| [Baekjoon] 백준 12865: 평범한 배낭 - Java (0) | 2025.06.22 |
|---|---|
| [Baekjoon] 백준 1092: 배 - Java (0) | 2024.10.17 |
| [Baekjoon] 백준 7662: 이중 우선순위 큐 - Java (0) | 2024.09.22 |
| [Baekjoon] 백준 1038: 감소하는 수 - Java (0) | 2024.09.16 |
| [Baekjoon] 백준 1011: Fly me to the Alpha Centauri - Java (0) | 2024.09.14 |