1. 문제
9935번: 문자열 폭발
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모
www.acmicpc.net
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
2. 풀이
1. stack으로 문자열을 하나씩 저장하다가 폭발 문자열의 끝 문자열과 동일하다면 remove메서드를 호출한다.
2. remove메서드는 stack의 끝부터 하나씩 폭발 문자열과 비교하며 pop시킨다. 만약 중간에 stack이 비었거나 폭발문자열과 다른 문자열이 stack에 있다면 반복을 멈추고 해당 위치+1부터 폭발 문자열 끝까지 다시 push한다.
import java.io.*;
import java.util.Stack;
public class BOJ_9935_문자열폭발 {
static Stack<Character> stack = new Stack<>();
static char[] bomb;
static int len;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
char[] str = in.readLine().toCharArray();
bomb = in.readLine().toCharArray();
len = bomb.length;
for(char ch:str){
stack.push(ch);
if(ch==bomb[len-1]){
remove();
}
}
if(stack.size()==0) {
System.out.println("FRULA");
return;
}
StringBuilder answer = new StringBuilder();
while(!stack.empty()) answer.append(stack.pop());
System.out.println(answer.reverse());
}
public static void remove(){
for(int i=len-1;i>=0;i--){
if(stack.empty() || stack.peek()!=bomb[i]){
for(int j=i+1;j<len;j++){
stack.push(bomb[j]);
}
return;
}else{
stack.pop();
}
}
}
}
3. 결과
첫번째 코드는 이거였는데, 어쩐지 너무 간단하다 싶었다.. 메모리제한을 신경써서 봐야겠다.
(사실 힌트를 보기 전까지는 이 문제를 stack으로 풀거라고 상상못했다. 더 공부해야겠다 ..!)
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String str = in.readLine();
String bomb = in.readLine();
while(str.contains(bomb)){
str = str.replaceAll(bomb,"");
}
if(str.length()==0) System.out.println("FRULA");
else System.out.println(str);
}
}
두번째로 틀린 emptystack은 빈 스택일 때 peek()메서드가 에러난다는 걸 고려하지 않아서였다. 그 부분만 수정해주니 맞았다.
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 20310 타노스 - JAVA (0) | 2023.03.06 |
---|---|
[BOJ] 3473 교수가 된 현우 - JAVA (0) | 2023.03.05 |
[BOJ] 1325 효율적인 해킹 - JAVA (0) | 2023.03.03 |
[BOJ] 2210 숫자판 점프 - JAVA (0) | 2023.03.02 |
[BOJ] 1806 부분합 - JAVA (0) | 2023.02.28 |
댓글