문제 링크
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}
문제 설명
접근 방법
이 문제에 핵심
1. 폭발 문자열에는 같은 문자를 2개 이상 포함하지 않는다.
2. 폭발 문자열이 되면 폭발한 뒤 남은 문자열을 붙입니다.
3. 모든 폭발이 끝난 뒤 문자열에 아무것도 문자가 남지 않으면 "FRULA"을 결과로 출력합니다.
문제를 처음 접근할 때 시간복잡도만 집중하여 HashMap과 Stack을 사용하여서 폭발이 진행되고 붙일 때에도 바로 폭발 문자열이 만들어지는지 확인하도록 처음에 구현하였지만 메모리 초과로 실패하였습니다.
그래서 단순하게 접근을 하면서 문자열에 각 글자가 폭발 문자열에 마지막 글자와 동일할 때 이전에 글자들을 탐색하여 폭발 문자열인지 확인하고 폭발 문자열이면 폭발하도록 하였습니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 문자열에서 폭발 문자열에 해당하는 곳을 폭발시킨 뒤 붙이는 작업을 반복합니다.
3. 폭발이 종료된 뒤 문자열의 상태에 따라 결과를 출력합니다.
폭발
문자열에 글자들을 순차적으로 쌓아놓기 위해서 Stack(LIFO)을 이용하였습니다.
문자열에서 폭발 문자열이 마지막 글자와 동일한 곳까지 Stack에 저장합니다.
Ex)
문자열 : 112ab2
폭발 문자열 : 12ab
마지막 폭발 글자 : b
마지막 폭발 글자와 동일한 곳까지 Stack에 저장!
b(5) |
a(4) |
2(3) |
1(2) |
1(1) |
폭발 문자열인지 탐색!
탐색 범위
2 ≤ n ≤ 5 (Stack크기 - 폭발 문자열 길이 ≤ n ≤ Stack 크기)
= 12ab
폭발 문자열로 성립! 폭발!
1(1) |
이후 문자열 다시 탐색!
2(2) |
1(1) |
예제입력 1.
1. 입력된 정보를 저장합니다.
문자열 : mirkovC4nizCC44
폭발 문자열 : C4
2. 문자열에서 폭발 문자열에 해당하는 곳을 폭발시킨 뒤 붙이는 작업을 반복합니다.
mirkovC4nizCC44
폭발 문자열 마지막 글자인 곳까지 탐색!
4(8) |
C(7) |
v(6) |
o(5) |
k(4) |
r(3) |
i(2) |
m(1) |
폭발 문자열인지 탐색!
2 ≤ n ≤ 5
= C4
폭발!
v(6) |
o(5) |
k(4) |
r(3) |
i(2) |
m(1) |
다시 탐색!
4(12) |
C(11) |
C(10) |
z(9) |
i(8) |
n(7) |
v(6) |
o(5) |
k(4) |
r(3) |
i(2) |
m(1) |
폭발 문자열인지 탐색!
11 ≤ n ≤ 12
= C4
폭발!
C(10) |
z(9) |
i(8) |
n(7) |
v(6) |
o(5) |
k(4) |
r(3) |
i(2) |
m(1) |
다시 탐색!
4(11) |
C(10) |
z(9) |
i(8) |
n(7) |
v(6) |
o(5) |
k(4) |
r(3) |
i(2) |
m(1) |
폭발 문자열인지 탐색!
10 ≤ n ≤ 11
= C4
폭발!
z(9) |
i(8) |
n(7) |
v(6) |
o(5) |
k(4) |
r(3) |
i(2) |
m(1) |
폭발 종료!
3. 폭발이 종료된 뒤 문자열의 상태에 따라 결과를 출력합니다.
Stack이 비어있으면 모두 폭발된 것이지만 남아있기 때문에 Stack에 저장된 정보를 출력합니다.
mirkovniz을 결과로 출력합니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- 문자열을 탐색하여 폭발 문자열이 존재하는지 확인합니다.
- 폭발 문자열이면 폭발을 진행시키는 것을 반복합니다.
- 폭발이 모두 종료 된 뒤 현재 문자열에 따라 결과를 BufferedWriter 저장하였습니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
※문자열이 폭발 문자열보다 길이가 작으면 절대 폭발이 일어나지 않기 때문에 입력된 문자열을 그대로 출력합니다.
import java.io.*;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
//입력값 저장하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Stack<Character> stack = new Stack<>(); //글자 저장할 Stack
String input = br.readLine(); //문자열
String word = br.readLine(); //폭발 문자열
//문자열이 폭발 문자열보다 길이가 작으면 폭발할 일이 없습니다.
if (word.length() > input.length()) {
bw.write(input);
} else {
//문자열 탐색
for (int i = 0; i < input.length(); i++) {
stack.add(input.charAt(i));
//글자가 폭발 문자열에 마지막 글자인지 확인
if (stack.size() >= word.length() && stack.peek() == word.charAt(word.length()-1)) {
boolean check = false;
//폭발 문자열인지 확인
for (int j = 0; j < word.length(); j++) {
if (stack.get(stack.size() - word.length() + j) != word.charAt(j)) {
check = true;
break;
}
}
//폭발 문자열일 때 Stack에 저장된 정보 폭발시키기
if (!check) {
for (int j = 0; j < word.length(); j++)
stack.pop();
}
}
}
//Stack에 저장된 정보 저장
StringBuilder answer = new StringBuilder();
for(Character c : stack)
answer.append(c);
//문자열이 폭발된 후에도 남아있을 경우
if(answer.length()>0)
bw.write(answer.toString());
else //문자열이 모두 폭발 되었을 때
bw.write("FRULA");
}
bw.flush(); //결과 출력
bw.close();
br.close();
}
}
'백준' 카테고리의 다른 글
[백준] 알고리즘 분류(트리,JAVA)1068번, 트리 (0) | 2022.09.25 |
---|---|
[백준] 알고리즘 분류(문자열,JAVA)10824번, 네 수 (0) | 2022.09.24 |
[백준] 알고리즘 분류(문자열,JAVA)7567번, 그릇 (0) | 2022.09.22 |
[백준] code.plus(브루트 포스 Part 2,JAVA)16987번, 계란으로 계란치기 (0) | 2022.09.21 |
[백준] 알고리즘 분류(문자열,JAVA)15829번, Hashing (2) | 2022.09.20 |
댓글