[Java+Python]9935번, 문자열 폭발

목차

 

문제

 

상근이는 문자열에 폭발 문자열을 심어 놓았다.

폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다.
• 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

 

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

 

입력

 

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1,..., 9로만 이루어져 있다.

 

출력

 

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

 

풀이

 

스택 2 단계의 첫 문제이다. 그러나 이번 문제에선 직접 스택이나 어레이덱을 사용하지 않는다.

 

이 문제는 지정된 '폭발 문자열'을 찾아 제거하는 문제이다.

 

입력으로 주어진 문제에서 '폭발 문자열'이 더 이상 존재하지 않을 때까지 해당 문자열을 반복해서 제거한다.

 

이를 위해 스택 자료구조를 사용할 수도 있지만, 여기선 char[] 배열을 스택처럼 사용하기로 한다.

 

문제 풀이를 요약하면 매우 간단한데, 스택에 문자를 추가하고 각 단계에서 폭발 문자열인지 검사한다.

 

이 과정을 모두 마치고 스택에 남아있는 문자가 답이 된다.

 

항상 말로만 알고리즘을 설명하려니 쉽지 않았는데, 이번 글부터는 코드 조각을 사용해서 적어보려고 한다.

 

코드를 구성하는 알고리즘은 아래와 같다.

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] text = br.readLine().toCharArray();
		char[] explosion = br.readLine().toCharArray();
		char[] result = new char[text.length];
		int idx = 0;

주어진 입력의 첫 줄을 text, 두 번째 줄을 explosion이라는 이름의 char[]로 변환한다.

 

또한 결과를 저장할 배열 result와 idx를 초기화한다. 여기서 idx는 result 배열에서 현재 채워 넣은 부분,

 

그러니까 가장 마지막 부분의 인덱스를 가리키게 된다.

		for (char c : text) {
			result[idx] = c;

향상된 for문을 이용해서 text의 각 문자 c를 result 배열의 idx 인덱스에 저장한다.

 

이 부분이 스택의 push와 같은 역할을 한다.

			if (isExplosive(result, explosion, idx)) {
				idx -= explosion.length;
			}
			idx++;
		}

이어서 isExplosive 메서드를 호출해서 방금 추가된 부분이 폭발 문자열과 일치하는지 검사한다.

 

만약 일치한다면 idx를 폭발 문자열의 길이만큼 감소시킨다. 이 부분은 요소를 pop 하는 것과 동일하다.

 

일치하지 않는다면 idx를 1 증가시킨다.

 

isExplosive는 다음과 같이 구현된다.

	private static boolean isExplosive(char[] result, char[] explosion, int idx) {

		if (idx < explosion.length - 1) {
			return false;
		}

		for (int i = 0; i < explosion.length; i++) {
			if (explosion[i] != result[idx - explosion.length + 1 + i]) {
				return false;
			}
		}

		return true;
	}

우선 result, explosion, idx를 매개변수로 받는다.

		if (idx < explosion.length - 1) {
			return false;
		}

이어서 idx가 폭발 문자열의 길이보다 작은 경우, 즉 result 배열의 길이가 폭발 문자열의 길이보다 작은 경우

 

폭발 문자열과 일치할 가능성이 없기 때문에 false를 반환한다.

		for (int i = 0; i < explosion.length; i++) {
			if (explosion[i] != result[idx - explosion.length + 1 + i]) {
				return false;
			}
		}

그렇지 않다면 result배열의 마지막 부분과 폭발 문자열을 한 글자씩 비교한다.

 

일치하지 않는 문자가 있다면 폭발 문자열이 아니므로 false를 반환한다.

return true;
}

이를 통과하고, 모든 문자가 일치한다면 true를 반환한다. 이는 현재까지 추가된 문자열의 마지막 부분이

 

폭발 문자열과 일치한다는 의미이다.

		System.out.println(idx == 0 ? "FRULA" : String.valueOf(result, 0, idx));

모든 과정이 끝나면 idx가 0인지 판별한다.

 

만약 0이라면 "FRULA"를 출력하고, 그렇지 않다면 result배열에서 idx까지의 요소를 출력한다.

 

스택에 남아있는 요소를 전부 출력하는 것이라고 생각할 수 있다.

 

Java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] text = br.readLine().toCharArray();
		char[] explosion = br.readLine().toCharArray();
		char[] result = new char[text.length];
		int idx = 0;

		for (char c : text) {
			result[idx] = c;
			if (isExplosive(result, explosion, idx)) {
				idx -= explosion.length;
			}
			idx++;
		}

		System.out.println(idx == 0 ? "FRULA" : String.valueOf(result, 0, idx));
	}

	private static boolean isExplosive(char[] result, char[] explosion, int idx) {

		if (idx < explosion.length - 1) {
			return false;
		}

		for (int i = 0; i < explosion.length; i++) {
			if (explosion[i] != result[idx - explosion.length + 1 + i]) {
				return false;
			}
		}

		return true;
	}
}

 

Python

 

import sys

text = list(sys.stdin.readline().rstrip())
explosion = list(sys.stdin.readline().rstrip())
result = [0 for _ in range(len(text))]
idx = 0


def isExplosive(result, explosion, idx):
    if idx < len(explosion) - 1:
        return False

    for i in range(len(explosion)):
        if explosion[i] != result[idx - len(explosion) + 1 + i]:
            return False

    return True


for c in text:
    result[idx] = c

    if isExplosive(result, explosion, idx):
        idx -= len(explosion)

    idx += 1

print("FRULA" if idx == 0 else "".join(result[:idx]))

 

Performance