[BOJ] 백준 9935번 : 문자열 폭발 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

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

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

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

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

입력

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

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

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

 

풀이

문자열 처리와 관련된 문제였습니다. 그리고 문자열의 최대 길이는 10^6이기때문에 문자열을 하나 하나 확인하는 O(N^2)으로 풀면 시간초과가 날 수 밖에 없었습니다. 따라서, O(N^2)보다 빠른 방식을 택해야했습니다.

제가 푼 로직은 다음과 같습니다.

1. 문자열(str)에서 첫 번째 문자부터 차례 차례 검사한다.

2. 폭발 문자열(explosion)의 맨 마지막 글자와 str에서 현재 검사하는 문자와 같다면, 아래와 같은 작업을 취한다.

2-1. 폭발 문자열의 맨 마지막 글자를 제외한 나머지 앞 글자와 str의 앞 글자를 비교하면서, str 안에 폭발 문자열이 들어있는 것이 맞는지 확인한다.

3. 2번 혹은 2-1번에 해당하지 않을 경우, output에 현재 문자를 이어붙인다.

 

아래 예제를 보면서 다시 이해해 봅시다.

 

예제

str = "1abcd"

explosion = "abcd"

 

위와 같은 예제가 있다고 가정합시다.

처음에 output은 char[] output = new char[str.length()]로 정의합니다. 그리고 output의 문자열의 길이를 index로 표현합시다. 

str의 첫 번째 문자부터 차례 차례 마지막 문자까지 검사해 보도록 하겠습니다.

먼저, 첫 번째 문자는 '1'이고, 폭발 문자열의 'd'와 같지 않으므로 output[0] = '1'을 추가합니다. 그리고 index를 1 증가시킵니다.

같은 방식으로 output[1] = 'a', output[2] = 'b', output[3] = 'c'가 채워질 것입니다.

마지막 문자는 'd'이고, 이것은 폭발 문자열의 맨 끝과 같습니다. (이 때, index = 4 상황입니다.)

따라서, (index - 1)번째부터 (index - 3)번째까지 explosion의 2번째, 1번째, 0번째 인덱스의 값이 서로 같은지 확인해야합니다.

위에 경우에서는 값이 서로 같기때문에 index의 값을 폭발 문자열 바로 앞에 해당하는 부분으로 바꿔주어야 합니다.

즉, index = index - (explosion.length() - 1) = 4 - (4 - 1) = 1이 됩니다.

마지막 문자까지 검사가 완료되었으므로 index의 개수만큼 output의 요소를 출력하면 됩니다.

index = 0이 아니라 1이므로 '1'을 출력하는 것이 정답입니다.

 

아래는 위 과정을 소스코드로 정리한 것입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();
        String explosion = br.readLine();
 
        char[] output = new char[str.length()];
        int index = 0; // output의 index
 
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            // 폭발 문자열의 맨 끝과 c가 같은 경우
            if (explosion.charAt(explosion.length() - 1) == c) {
                if (index < explosion.length() - 1) { // output에서 폭발 문자열을 검사할 만큼의 길이가 확보되어있지 않은 경우.
                    output[index++] = c; // output에 c를 이어 붙임.
                } else { // output에서 폭발 문자열을 검사할 만큼의 길이가 확보되어있는 경우.
                    boolean ok = true;
                    // output에서 c를 기점으로 그 앞쪽 문자열이 폭발 문자열과 동일한지 확인.
                    for (int j = index - 1, k = explosion.length() - 2; k >= 0; j--, k--) {
                        if (output[j] != explosion.charAt(k)) { // 폭발 문자열과 다른 문자가 있음.
                            ok = false;
                            break;
                        }
                    }
 
                    if (ok) { // 폭발 문자열과 일치함.
                        index = index - (explosion.length() - 1); // index를 폭발 문자열 이전으로 되돌림.
                    } else { // 폭발 문자열과 일치하지 않음.
                        output[index++] = c; // output에 c를 이어 붙임.
                    }
                }
            } else { // 폭발 문자열의 맨 끝과 c가 다른 경우
                output[index++] = c; // output에 c를 이어 붙임.
            }
        }
 
        StringBuilder ans = new StringBuilder();
        if (index == 0) { // output에 문자열이 들어있지 않은 경우.
            ans.append("FRULA");
        } else { // output에 문자열이 들어있는 경우.
            for (int i = 0; i < index; i++) {
                ans.append(output[i]);
            }
        }
 
        bw.write(ans.toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.