[BJ] 9935. 문자열 폭발.java

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

1. Stack과 Deque를 이용한 풀이(오답)

1-1) 큐를 사용한 풀이(오답)

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;



public class Main {
    public static Queue<Character> queue;

    public static Character number[];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        queue = new ArrayDeque<>();

        String str = br.readLine();

        for(int i = 0; i<str.length(); i++){
            queue.add(str.charAt(i));
        }

        str = br.readLine();

        number = new Character[str.length()];

        for(int i = 0; i<str.length(); i++){
            number[i] = str.charAt(i);
        }

        int idx = 0, len = 0;
        char c;
        boolean compare = true;

        Queue<Character> tempQueue = new ArrayDeque<>();

        while(compare){
            //System.out.println("size : "+queue.size());
            compare = false; // 찾으면 true로 바꿔줌
            len = queue.size();

            idx = 0;
            tempQueue.clear();

            while(len-- != 0){
               c = queue.poll();

               if(number[idx] == c){
                   idx++;
                   tempQueue.add(c);
               }else{
                   while(!tempQueue.isEmpty()) {
                       queue.add(tempQueue.poll());
                   }

                   idx = 0;

                   if(number[idx] == c){
                       idx++;
                       tempQueue.add(c);
                   }else{
                       queue.add(c);
                   }
               }

               if(idx == number.length){
                   compare = true;
                   idx = 0;
                   tempQueue.clear();
               }
            }

        }

        if(queue.isEmpty()){
            System.out.println("FRULA");
        }else{
            StringBuilder sb = new StringBuilder();
            while(!queue.isEmpty()){
                sb.append(queue.poll());
            }
            System.out.println(sb.toString());
        }



    }


}

1-2) Deque를 사용한 풀이

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;



public class Main {
    public static Deque<Character> dq;

    public static Character number[];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        dq = new ArrayDeque<>();

        String str = br.readLine();

        for(int i = 0; i<str.length(); i++){
            dq.add(str.charAt(i));
        }

        str = br.readLine();

        number = new Character[str.length()];

        for(int i = 0; i<str.length(); i++){
            number[i] = str.charAt(i);
        }

        int idx = 0, len = 0;
        char c;
        boolean compare = true;

        while(compare){
            //System.out.println("size : "+queue.size());
            compare = false; // 찾으면 true로 바꿔줌
            len = dq.size();

            idx = 0;

            while(len-- != 0){
               c = dq.pollFirst();

               if(number[idx] == c){
                   idx++;
               }else{
                   idx = 0;
                   if(number[idx] == c){
                       idx++;
                   }
               }

               dq.addLast(c);

               if(idx == number.length){
                   compare = true;

                   idx = 0;

                   for(int i = 0; i<number.length; i++){
                       dq.pollLast();
                   }
               }
            }

        }

        if(dq.isEmpty()){
            System.out.println("FRULA");
        }else{
            StringBuilder sb = new StringBuilder();
            while(!dq.isEmpty()){
                sb.append(dq.pollFirst());
            }
            System.out.println(sb.toString());
        }



    }


}

---

2. Stack을 사용함(정답)

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;



public class Main {

    public static String str1, str2;

    public static Stack<Character> stack;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        str1 = br.readLine();

        str2 = br.readLine();

        stack = new Stack<>();

        boolean ischeck = true;
        for(int i = 0; i < str1.length(); i++){
            stack.push(str1.charAt(i));


            if(stack.size() >= str2.length()){
                ischeck = true;
                for(int j = 0; j<str2.length(); j++){
                    if(stack.get(stack.size() - str2.length() + j) != str2.charAt(j)){
                        ischeck = false;
                        break;
                    }
                }

                if(ischeck){
                    for(int j = 0; j<str2.length(); j++){
                        stack.pop();
                    }

                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for(char ch : stack){
            sb.append(ch);
        }

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



    }


}

• 문제에서 사용한 메소드
  - stack에서 값을 꺼내서 비교하는 것이 아닌 get(idx) 메소드를 사용하여 idx번째에 있는 문자를 비교할 수 있었다.

• 문제 풀이
  - stack이 폭발 문자열의 길이를 초과할 때마다 stack의 제일 위에서 부터 폭발 문자열 만큼의 길이까지 문자를 비교한다. (하나라도 다르면 false)