[백준] 9935 문자열 폭발 - Data Structure / Java

• 문제 링크

9935번: 문자열 폭발

 

• 풀이 과정

입력받은 문자열이 폭발 문자열과 일치할 경우 해당 문자열을 제거하기 위해 Stack 자료구조를 활용해 풀이한다.

 

입력받은 문자열을 하나씩 스택에 저장하는 중, 스택의 크기가 폭발 문자열의 길이보다 크거나 같을 경우,

스택에 저장된 문자열 중 폭발 문자열의 존재 여부를 나타낼 flag 변수를 생성해 탐색한다.

 

현재 문자열의 길이에서 폭발 문자열의 길이를 뺀 수를 시작 인덱스로써,

폭발 문자열의 길이만큼 탐색해 일치 여부를 확인한다.

예시로 현재 문자열의 길이가 8 이고 폭발 문자열의 길이가 2 일시,

8 - 2 + 0 = 6, 8 - 2 + 1 = 7 의 수식에 의해 스택의 인덱스 6 ~ 7 범위를 검사한다.

 

이때 범위 내 검사한 문자열이 불일치 시 flag 를 false 로 변경 및 반복문을 탈출 후 스택에 다음 문자 저장을 계속하며,

일치 시 flag 변수가 true 로 유지되어 스택 상단의 폭발 문자열을 제거 후 다음 문자를 이어서 저장한다.

 

끝으로 스택에 저장된 문자열을 StringBuilder 객체 sb 에 저장하고

삼항 연산자로 sb 의 값의 존재 유무를 판별해 "FRULA" 또는 sb 객체를 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String input = br.readLine();
		String exp = br.readLine();
		int expLen = exp.length();

		Stack<Character> stk = new Stack<>();
		for (int i = 0; i < input.length(); i++) {
			stk.push(input.charAt(i));

			if (stk.size() >= expLen) {
				boolean flag = true;

				for (int j = 0; j < expLen; j++) {
					if (stk.get(stk.size() - expLen + j) != exp.charAt(j)) {
						flag = false;
						break;
					}
				}

				if (flag) {
					for (int j = 0; j < expLen; j++)
						stk.pop();
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		for (Character c : stk)
			sb.append(c);

		bw.write(sb.length() == 0 ? "FRULA" : sb + "\n");
		bw.flush();
	}

}