[백준 / JAVA] 9935. 문자열 폭발 (G4)

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

 

처음엔 디큐(남들은 데크라고 함) 두 개를 써서 풀려고 했다. 두 디큐를 왔다갔다 하면서 뒤에서 빼줬다. 어차피 문자열 100만자 해봤자 200만 바이트 즉 2메가인데 메모리는 생각 자체를 안했다.  그리고 메모리가 터졌다. 내 속도 터졌다.

 

일주일이 지났다. 기부니가 안조아서 종일 누워있다가 스트레스 하나라도 해소할 겸 문제를 열었다. 디큐는 가변 메모리구조나 하나를 쓰든 두개를 쓰든 똑같겠지만 디큐를 하나만 써봤다. 메모리 초과가 났다. ArrayList 디큐가 LinkedList보다

메모리를 적게 쓴대서(속도는 더 느린걸로 암) 바꿨다. 시간초과가 났다.(2차위기)

 

코드를 다 지우고 문제의 비밀을 파헤쳤다. 이 문제의 비밀은 입력을 앞에서부터 읽으면서 바로바로 처리해도 결과가 같다는 것이였다. 자료구조 버리고 문자열로 갔다. Bufferedwriter도 사용했다. 숏코딩으로 깔끔하게 풀렸다. 기분굿.

 

기부니가 안좋았던 이유: 신차검수 갔는데 단차가...그림자가 져요 (인수거부)

 

내 속 폭발

 

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringBuilder input, answer;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		input = new StringBuilder(br.readLine());
		answer = new StringBuilder();
		String bomb = br.readLine();
		for (int i = 0; i < input.length(); i++) {
			answer.append(input.charAt(i));
			if (input.charAt(i) == bomb.charAt(bomb.length() - 1) && answer.length() >= bomb.length())
				if (answer.substring(answer.length() - bomb.length()).equals(bomb))
					answer.delete(answer.length() - bomb.length(), answer.length());
		}
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(answer.length() == 0 ? "FRULA" : answer.toString());
		bw.flush();
	}
}