BOJ 9935
2020-10-25
위 문제는 백준 사이트의 알고리즘 9935 문제에 관한 설명입니다.
문제
상근이는 문자열에 폭발 문자열을 심어 놓았다.
폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다.
남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, …, 9로만 이루어져 있다.
출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
소스코드
package day1025;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.next(); // 기준이 되는 문자열
String bomb = scanner.next();// 폭발이되는 문자열
char[] answer = new char[1000001]; // 1보다 크고 1000000보다 작다는 조건.
int length = bomb.length();// 1~36보다 작거나 같다는 조건.
char[] bombElement = new char[length];//폭발이 되는 문자열의 요소들을 넣을 곳 입니다.
for (int i = 0; i < bomb.length(); i++) //하나씩 옮겨담습니다.
bombElement[i] = bomb.charAt(i);
int index = 0;
for (int i = 0; i < str.length(); i++) {
answer[index++] = str.charAt(i);// str에 있는 것을 하나씩 옮겨담습니다.
if (answer[index - 1] == bombElement[length - 1]) {
//넣었을때 index-1번째 (= 마지막에 넣은 글자)와 bomb의 마지막 글자가 같다면
if (index - length < 0)// 현재까지 넣은 문자열의 갯수가 폭발 단어보다 짧다면
continue;//폭발이 일어나지 않습니다.
boolean flag = false; // 폭발
for (int j = 0; j < length; j++) {//폭발하는 단어의 길이만큼 반복합니다.
if (answer[index - 1 - j] != bombElement[length - 1 - j]) {
//넣은 문자열의 마지막 단어부터 폭발하는 문자를 하나씩 비교하는데
//다른문자가 있다면 그것은 폭발하는 단어가 아닙니다.
flag = true; // 불발
break;
}
}
if (!flag)//폭발한다면
index -= length; // index에서 폭발하는 단어의 길이만큼 빼줍니다.(폭발)
// 예) mirkovC4 에서 폭발단어 길이 2만큼 빼면 mirkov부터 다시 하나씩 채워감.
}
}
if (index == 0)//만약 폭발이 연쇄적으로 다 터져서 입력된 단어가 없다면
System.out.println("FRULA");
else {//단어가 있다면 끝까지 출력합니다.
for (int i = 0; i < index; i++)
System.out.print(answer[i]);
}
scanner.close();
}
}
이번문제는 문제열 처리 문제입니다.
자세한 설명은 주석으로 달아놓았습니다!