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();
	}
}

이번문제는 문제열 처리 문제입니다.

자세한 설명은 주석으로 달아놓았습니다!

문자열 폭발