[PS] 백준 문자열 폭발 java 풀이

9935번: 문자열 폭발 (acmicpc.net)

문제 접근

문자열 길이가 1,000,000보다 작으니..

nlogN 미만의 시간복잡도를 가지는 풀이를 해야하는 것인가?

 

문자열을 스택에 넣다가 폭발 문자열과 겹치기 시작하면 넣지말고?

완전 일치하면 그 만큼 스택에서 빼고?

그런데 빼고나서 다시 폭발 문자열이랑 일치하면 어떻게 검사하지? 다시 처음부터 검사하면 시간 복잡도가 늘어날텐데..

 

문제 해결

1. 문자열을 하나하나 StringBuilder(sb)에 넣으면서
2. sb의 크기가 폭발 문자열 길이보다 같거나 커지면
3. sb 끝에서 폭발 문자열 길이만큼 뺀 인덱스부터 검사 시작
4. 모두 같으면 그 부분만큼 delete
5. 다시 1번부터 반복하면, 끝에서부터 폭발 문자열 길이만큼 되돌아가서 검사하기 때문에 중간에 문자열이 삭제되도 다시 검사하게 된다.
6. O(n)으로 해결

코드

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

public class Main {

	static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String sentence = br.readLine();
		String bomb = br.readLine();
		int bombSize = bomb.length();
		StringBuilder sb = new StringBuilder();

		for (char c : sentence.toCharArray()) {
			sb.append(c);
			if (sb.length() >= bombSize) {
				boolean isBomb = true;
				for (int i = 0; i < bombSize; i++) {
					if (sb.charAt(sb.length() - bombSize + i) != bomb.charAt(i)) {
						isBomb = false;
					}
				}
				if (isBomb) {
					sb.delete(sb.length() - bombSize, sb.length());
				}
			}
		}

		if (sb.length() == 0) {
			System.out.println("FRULA");
		} else {
			System.out.println(sb);
		}

	}

}