[백준] 9935 문자열 폭발 - 자바

https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

문제 풀이

간단하게 풀기 위해 String.replace()를 사용해보고, 문자열 비교 후 뒤로 돌아가서 비교하는 방법 모두 해봤지만 다 시간초과가 발생했다.

스택을 사용한다고 해서 시간복잡도의 이점이 좋아지진 않는다.

따라서 이 문제는 어떻게 폭발 문자열을 비교할 것인지가 관건이다.

 

제가 처음 접근한 방법은 기존 문자열에서 폭발문자열의 길이만큼 서브스트링으로 반환하여 폭발문자열과 비교하는 것이다.

하지만 이 과정에서 불필요한 연산이 생긴다. 아래와 같은 입력이 들어왔다고 가정해보자

먼저 문자열 비교를 위해 abaa를 서브스트링으로 받는다. 그러고 폭발 문자열 abcd과 비교한다. 다음 반복문에선 baab와 폭발 문자열 abcd와 비교한다. 즉 첫 번째 abaa는 ab이후에 c와 같지 않기 때문에 abaa의 aa는 굳이 필요하지 않다. 다음 baab는 첫 번째 문자부터 다르기 때문에 이를 비교하기 위해 서브 스트링으로 변환하고 equals를 통해 연산하는 과정은 불필요한 오버헤드를 발생시킨다.

 

이를 개선하기 위해 귀찮더라도 우리는 문자열이 아닌 문자를 비교하면 된다.

 

그림으로 보면 대충 이런 느낌이다. 첫 abcd를 삭제하기 까지의 과정이다.

코드

package 백준;

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

public class b9935 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String boom = br.readLine();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            sb.append(ch);
            if (sb.length() >= boom.length()) {    // sb의 길이가 boom 이상이 되면 확인
                boolean isSame = true;
                for (int j = 0; j < boom.length(); j++) {
                    char ch1 = sb.charAt(sb.length() - boom.length() + j);
                    char ch2 = boom.charAt(j);
                    if (ch1 != ch2) {
                        isSame = false;
                        break;
                    }
                }
                if (isSame) {
                    // 폭발 문자열 삭제
                    sb.delete(sb.length() - boom.length(), sb.length());
                }
            }
        }

        System.out.println(sb.length() == 0 ? "FRULA" : sb);
    }
}

코드 풀이

기존 문자열에서 하나씩 sb에 넣으며 뒤에 쌓인 문자열 중 폭발문자열이 있다면 제거해 나간다.