백준 9935번, 문자열 폭발

헷갈린 것
for()~문을 활용하여 간단하게 문자를 읽어들일 수 있었지만, while()에 대한 집착이 문제 풀이의 시간을 증가시켰습니다. 또, 자바의 가비지 컬렉션만 믿고 메모리 관리에 소홀히 한다면 큰 문제를 발생시킬 수 있다는 것을 배울 수 있었습니다. 그리고 stack 구조에서 무식하게 get()을 난사하다가는 시간 복잡도의 구렁텅이로 빠질 수 있다는 것도요.

핵심) 폭탄은 반드시 재료가 모두 모여야지 폭발한다. (당연한 얘기지만)

첫 시도는 while()과 stack을 활용한 뇌코딩을 그대로 옮겨온 방식이었습니다. (아직 뇌코딩이 익숙하지 않아 메모장에서 여러 예시를 돌려가며 만들었습니다. 정말 뇌코딩은 숙련자의 영역인 것 같네요)

주어진 문자를 뒤에서부터 읽으며, stack에 차곡차곡 쌓는데, 만약 stack의 크기가 폭탄의 크기보다 작으면 계속해서 쌓습니다. 그러다가 폭탄의 크기와 같아지면, 폭탄의 크기만큼 스택에서 문자를 확인(get(i))하고 폭탄이 완성되었다면 pop()해주는 방식을 사용했습니다.

여기서 문제는, stack.get(n)의 시간 복잡도였습니다. O(N)을 갖는데, 폭탄의 크기가 커지면 커질수록 정말 말도 안 되는 시간 복잡도를 갖게 됩니다. 따라서, 저는 Deque 자료구조를 사용하였습니다.

Deque 자료구조는 자료구조 칼럼에서 자세히 서술하겠습니다.
Deque를 통해 맨 뒤에서만 입출력을 진행하여 스택처럼 사용하였고, descendingIterator를 활용하여 시간 복잡도를 크게 줄였습니다.

그리고 문자열의 뒤부터 읽은 이유는, Deque도 뒤에서부터 꺼내고, 폭탄 확인 과정도 뒤에서부터 반복자를 돌리고, 집어넣는 것도 뒤에서부터 집어넣는데 그럼 뒤에서부터 확인하자!
라는 생각에 주어진 문자열의 뒤부터 확인했습니다. 앞에서부터 읽어도 전혀 상관 없습니다.
인덱스 관련해서 아주 약간만 변경하면 뒤에서부터 읽든, 앞에서부터 읽든 상관 없습니다.
논리 구조
주어진 문자열의 맨뒤를 차례대로 Deque의 뒷부분부터 넣습니다.(addLast, pollLast만 합니다.)
만약 Deque의 크기가 폭탄의 크기보다 같거나 크다면, 폭탄 검사를 실시합니다.
폭탄 검사는 Deque.descendingIterator()를 활용하여 폭탄 길이만큼 확인합니다.
Deque에서 꺼낸 문자와 폭탄의 문자가 같다면 check값을 증가시킵니다.
이 check값이 폭탄의 크기와 같다면, Deque에서 폭탄 크기만큼 pollLast()를 실행합니다.(문자 삭제)

위 작업을 반복 후, Deque에 남은 것을 결과로 출력합니다.

코드- 뒤에서부터 읽기)

public class P9935 {

	public static void main(String[] args) throws IOException {
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
		Deque<Character> dq = new ArrayDeque<>();

		char[] org = bfr.readLine().toCharArray();
		char[] boom = bfr.readLine().toCharArray();
		int orgLength = org.length;
		int boomLength = boom.length;
		StringBuilder result = new StringBuilder();

		for (int i = orgLength - 1; i >= 0; i--) {
			int check = 0;
			dq.addLast(org[i]);
			if (dq.size() >= boomLength) {
				Iterator<Character> rIt = dq.descendingIterator();
				int idx = 0;
				while(rIt.hasNext()) {
					if(idx >= boomLength)
						break;
					if(rIt.next() == boom[idx++])
						check++;
				}

				if (check == boomLength) {
					for (int j = 0; j < boomLength; j++) {
						dq.pollLast();
					}
				}
			}
		}

		int resultLength = dq.size();
		for (int i = 0; i < resultLength; i++) {
			result.append(dq.pollLast());
		}

		if (result.length() != 0)
			bfw.write(result.toString() + "\n");
		else
			bfw.write("FRULA\n");

		bfw.flush();
		bfw.close();
		bfr.close();
	}
}

코드- 앞에서부터 읽기)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
		Deque<Character> dq = new ArrayDeque<>();

		char[] org = bfr.readLine().toCharArray();
		char[] boom = bfr.readLine().toCharArray();
		int orgLength = org.length;
		int boomLength = boom.length;
		StringBuilder result = new StringBuilder();

		for (int i = 0; i < orgLength; i++) {
			int check = 0;
			dq.addLast(org[i]);
			if (dq.size() >= boomLength) {
				Iterator<Character> rIt = dq.descendingIterator();
				int idx = boomLength - 1;
				while (rIt.hasNext()) {
					if (idx < 0)
						break;
					if (rIt.next() == boom[idx--])
						check++;
				}

				if (check == boomLength) {
					for (int j = 0; j < boomLength; j++) {
						dq.pollLast();
					}
				}
			}
		}

		int resultLength = dq.size();
		for (int i = 0; i < resultLength; i++) {
			result.append(dq.poll());
		}

		if (result.length() != 0)
			bfw.write(result.toString() + "\n");
		else
			bfw.write("FRULA\n");

		bfw.flush();
		bfw.close();
		bfr.close();
	}
}