[Gold IV] 문자열 폭발 - 9935 (JAVA)

문제 요약

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

---

아래는 기존에 작성했던 코드다.

문제 분석

스택을 사용해서 푼다.

원본 문자열을 순차적으로 스택에 넣어주다가

폭발 문자열의 끝문자와 같은 문자를 스택에 넣게 되면

그때무터 폭발문자열의 역순으로 스택의 값을 빼가며 비교해 본다.

---

코드

package Week16;

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

public class BOJ_9935 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다
        char[] word = br.readLine().toCharArray();
        // 길이는 1보다 크거나 같고, 36보다 작거나 같다.
        char[] boom = br.readLine().toCharArray();
        // word가 순차적으로 들어갈 stack
        Stack<Character> stack = new Stack<>();
        // 임시로 비교할 데이터를 저장할 stack
        Stack<Character> tempStack = new Stack<>();
        // word의 문자를 순차적으로 stack안에 넣으며
        // boom의 끝 문자가 나올때를 기다린다.
        for(int i = 0; i < word.length; i++){
            char curr = word[i];
            // 현재 stack에 넣어야 하는 문자가 boom의 마지막 문자와 같다면?
            if(curr == boom[boom.length-1]){
                // stack안에 있는 문자열들이 지금 비교해야할 폭발 문자열길이 -1(이미 맨뒤는 비교했기때문에 -1)보다 작다면 
                // 이건 탐색할 필요가 없음.
                if(stack.size() < boom.length-1){
                    stack.push(curr);
                }
                else{
                    // 탐색작업 시작
                    // tempStack에 데이터를 순차저장한다.
                    tempStack.push(curr);
                    // boom의 맨 뒷자리는 이미 비교했으니, 뒤에서 두번째자리부터 비교한다.
                    for(int j = boom.length-2; j >= 0; j--){
                        // 여기서 stack.pop()했을때 EmptyStack에러가 난다. 에러처리를 해주자.
                        if(stack.isEmpty()){
                            stack.push(tempStack.pop());
                            break;
                        }
                        // stack이 비지 않았다면, 정상진행
                        char tempCurr = stack.pop();
                        // 같다면?
                        if(tempCurr == boom[j]){
                            tempStack.push(tempCurr);
                        }
                        // 다르다면? 즉시 멈추고, tempStack안에 있는 값들을 모두 stack안에 넣어준다.
                        else{
                            // 우선 방금 stack에서 pop한 tempCurr부터 stack안에 다시 넣어주고
                            stack.push(tempCurr);
                            // tempStack안에 있던 애들을 stack안에 다시 넣어준다.
                            while(!tempStack.isEmpty()){
                                stack.push(tempStack.pop());
                            }
                            // boom을 할 수 없으니 멈춰준다.
                            break;
                        }
                    }
                    // tempStack을 비어준다.
                    tempStack.clear();
                }
            }
            else{
                stack.push(curr);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(char c : stack){
            sb.append(c);
        }
        System.out.println(sb.length() > 0 ? sb.toString() : "FRULA");

    }
}

---

정리

새로 배운 내용

없음

개선할 점

1. 문제를 너무 복잡하게 풀었음.
2. 복잡하게 풀다 보니 히든을 통과하지 못했음

내가 통과하지 못했던 히든은
12341234
4123
이거였다.
내 코드가 폭발문자열의 끝값을 스택에 넣게 될 때, 그때부터 스택에서 값을 한 개씩 뽑아가며
폭발문자열과 같은 문자열인지 비교하는 로직인데,
만약 현재 스택에 담긴 값이 폭발문자열의 길이보다 작다면 그냥 지금까지 비교한 걸 기반으로 
끝까지 비교하지 않았는데도 맞다고 판단하고 넘겨버렸다.
그래서 조건문 하나 추가해서 해결했다.
근데 풀고 보니까 스택을 2개나 풀 이유가 없던문제였고, 로직도 너무 복잡했다.
너무 인간적으로 푼 거 아닌가 싶다. 
추후에 다시 풀어봐야겠다.

더 찾아볼만한 사항

없음

---

---

 

리팩토링 후 코드

package Week16;

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

public class BOJ_9935 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다
        char[] word = br.readLine().toCharArray();
        // 길이는 1보다 크거나 같고, 36보다 작거나 같다.
        char[] boom = br.readLine().toCharArray();
        StringBuilder sb = new StringBuilder();
        // word의 문자열 처음부터 넣어가며 확인해보자
        for(char curr : word){
            // 우선 현재 문자열을 sb안에 넣어준다.
            sb.append(curr);
            // 현재 문자가 boom의 끝문자와 같고, 문자열의 길이가 boom의 길이 이상이면 탐색
            if(curr == boom[boom.length-1] && sb.length() >= boom.length){
                // 폭발문자열인지 확인하기 위한 변수 생성
                boolean isBoom = true;
                // 폭발문자열 길이만큼 탐색하기 위한 반복문
                for(int j = 0; j < boom.length -1; j++){
                    // 폭발 문자열의 처음부터 끝까지를 sb에 해당하는 index의 값과 비교한 후
                    // 다른 값이 나온다면 false처리
                    if(sb.charAt(sb.length() - boom.length + j) != boom[j]){
                        isBoom = false;
                        break;
                    }
                }
                // 위에서 폭발문자열이란걸 확인했다면?
                if(isBoom){
                    // 그 만큼의 문자열을 지워준다.
                    sb.delete(sb.length() - boom.length, sb.length());
                }
            }
        }

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

추가로 색다른 방식으로 작성된 코드가 있어서 하나 남겨본다.

gmlwo308님이 작성하신 코드

https://www.acmicpc.net/source/62733142

로그인

import static java.lang.System.*;

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(in));
		char[] word = br.readLine().toCharArray();
		char[] boom = br.readLine().toCharArray();
		char[] res = new char[word.length];
		int idx = 0, j;
		for(int i = 0; i < word.length; i++, idx++){
			res[idx] = word[i];
			if(idx + 1 < boom.length) continue;
			for(j = 0; j < boom.length && res[idx - j] == boom[boom.length - j - 1]; j++);
			if(j == boom.length) idx -= j;
		}

		if(idx == 0) out.println("FRULA");
		else {
			StringBuilder sb = new StringBuilder();
			for(int i = 0; i < idx; i++) sb.append(res[i]);
			out.println(sb);
		}
	}
}