[백준 9935] 문자열 폭발 - Java 문제풀이

오늘의 1일 1골드 문제는 다음 문제이다.

 

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

9935번: 문자열 폭발

 

문제

문제

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

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

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

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

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

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

해설

이 문제는 왜인지 모르게 스택을 풀어야 정답이 되었다..

스택의 경우 get()함수를 사용해본 적이 없어서 몰랐는데, get() 함수를 사용하면 특정 인덱스의 값을 가져올 수 있었다.

이를  이용해서 스택에 하나씩 넣으면서 stack()의 사이즈가 폭발 문자열 길이보다 크거나 같다면 문자열을 하나씩 비교하여 직전에 넣은 문자열들이 폭발 문자열과 같다면 스택에서 삭제해주는 식이다. 이게 끝이다.. 정말 ...ㅎㅎ

 

다음은 코드 전문이다.

import java.util.Scanner;
import java.util.Stack;

public class BOJ_9935 {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        char[] str = sc.next().toCharArray();
        char[] bomb = sc.next().toCharArray();
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for(int i=str.length-1;i>=0;i--) {
            stack.push(str[i]);
            if (stack.size() >= bomb.length) {
                boolean flag = true;
                for(int j=bomb.length-1;j>=0;j--) {
                    if (stack.get(stack.size()-1-j)!=bomb[j]) {
                        flag=false;
                        break;
                    }
                }
                if (flag) {
                    for(int j=0;j<bomb.length;j++) stack.pop();
                }
            }
        }
        while(!stack.isEmpty()) sb.append(stack.pop());
        System.out.println(sb.length()==0?"FRULA":sb.toString());
    }
}

 

이 문제의 경우에는 내가 삽질한 기록을 같이 적으려고 한다.

1. 스택을 2개 사용하는 방법

인덱스 스택과 캐릭터 스택, 2개를 사용하였다. 인덱스를 사용하여, 현재 폭발 문자열에서 가리키는 인덱스의 문자와 현재 문자가 같다면 인덱스++ 해준다.(혹은 0이거나), 그렇지 않은 경우에는 인덱스에 -1을 넣어준다. 이 -1은 항상 스택에서 사라지지 않는 문자열을 의미한다.

만일 인덱스가 폭발 문자열의 길이와 같게 된다면 폭발 문자열의 길이만큼 stack을 pop 해준다. 그리고 인덱스를 인덱스 스택의 최 상단 인덱스+1 해준다. 그렇게 계속 초기화 해준 결과 메모리 초과가 난다. ㅋㅋㅋㅋㅋ

 

코드 전문보기 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String bomb = br.readLine();
        Stack<Integer> integerStack = new Stack<>();
        Stack<Character> characterStack = new Stack<>();
        int index = 0;
        for(int i=0;i<str.length();i++) {
//            System.out.println("i: "+i+" -> "+str.charAt(i)+"  index: "+index);
            if (bomb.charAt(0) == str.charAt(i)) {
                index = 0;
                integerStack.push(index++);
                characterStack.push(str.charAt(i));
                if (index == bomb.length()) {
                    for(int j=0;j<bomb.length();j++) {integerStack.pop();characterStack.pop();}
                    index = integerStack.isEmpty() ? 0 : integerStack.peek()+1;
                }
            } else if (bomb.charAt(index) == str.charAt(i)) {
                integerStack.push(index++);
                characterStack.push(str.charAt(i));
                if (index == bomb.length()) {
                    for(int j=0;j<bomb.length();j++) {integerStack.pop();characterStack.pop();}
                    index = integerStack.isEmpty() ? 0 : integerStack.peek()+1;
                }
            }  else {
                integerStack.push(-1);
                characterStack.push(str.charAt(i));
            }
        }
//        System.out.println("-----------------");
//        System.out.println(integerStack.toString());
//        System.out.println(characterStack.toString());
//        System.out.println("-----------------");
        String answer = "";

        if (integerStack.isEmpty()) System.out.println("FRULA");
        else {
            while(!characterStack.isEmpty()) answer = characterStack.pop()+answer;
        }
        System.out.println(answer);




    }
}

 

2. StringBuilder 이용하기

또 다른 방법으로 StringBuilder를 이용해보았다.

StringBuilder를 이용해여 현재 인덱스 부터의 문자열이 폭발 문자열과 같다면 해당 인덱스부터 폭발 문자열의 길이만큼 StringBuilder에서 삭제하는 방식이다. 그렇게 하면 코드는 import문까지 17줄로 매우 짧지만 46%에서 시간 초과가 나게 된다...ㅎ

 

코드 전문보기

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer str = new StringBuffer(br.readLine());
        String bomb = br.readLine();
        for(int i=str.length()-1;i>=0;i--) {
            if (str.charAt(i) == bomb.charAt(0) && i+bomb.length() <= str.length() && str.subSequence(i, i+bomb.length()).equals(bomb)) {
                str.delete(i, i+bomb.length());
            }
        }
        System.out.println(str.length()==0?"FRULA":str.toString());
    }
}

---

 

ㅎㅎ 엄청 고생했다... ㅠ 근데 정답이라고 떠서 엄청 기뻤다.. ㅎㅎ

그래서 2일간 1일 1골드를 못했다.. 하지만 삽질의 끝에 풀어서 뿌듯했고, 오랜만에 오래 붙잡고 있던 문제였다.