9935번:문자열 폭발(Java)

 

 

 처음에는 String과 contains, replace 함수를 사용해 풀었다. 그런데 메모리 초과가 났다. 문자열의 길이가 1,000,000이나 되는 것이 원인이라고 생각해 Stack을 사용해 풀었다.

 

 Stack<Chatacter>에 문자열을 하나씩 넣으면서 Stack에 폭탄이 들어가게 되면 그 부분만큼 pop()을 해 주었다.

 

 

stack의 크기가 폭탄 문자열의 길이 이상이 되었을 때부터 검사를 시작한다.

 

stack에서 폭탄 문자열이 시작되는 지점부터 폭탄 문자열이 끝나는 지점까지의 모든 문자가 같으면 stack은 현재 폭탄 문자열을 포함하고 있는 의미이기 때문에, find에 true를 넣고 stack의 크기에서 폭탄 문자열의 길이만큼을 뺸 것을 get() 해 문자를 얻고 이게 폭탄 문자열의 charAt()과 다르면 find를 false로 만들어주고 break를 해 주었다.

 

 find가 true라면 stack에서폭탄 문자열의 길이만큼 pop을 해 주었다.

Scanner scanner = new Scanner(System.in);
String target = scanner.next();
String bomb = scanner.next();
int blength = bomb.length();
Stack<Character> stack = new Stack<>();
StringBuilder result = new StringBuilder("");
boolean find;

for(int i = 0; i<target.length(); i++)
{
    stack.push(target.charAt(i));
    if(stack.size() >= blength)
    {
        find = true;
        for(int j = blength; j>0; j--)
        {
            if(!stack.get(stack.size()-j).equals(bomb.charAt(bomb.length()-j)))
            {
                find = false;
                break;
            }
        }
        if(find)
        {
            for(int j = 0; j<blength; j++)
            {
                stack.pop();
            }
        }
    }
}

 

 

 

 

전체 코드

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        String target = scanner.next();
        String bomb = scanner.next();
        int blength = bomb.length();
        Stack<Character> stack = new Stack<>();
        StringBuilder result = new StringBuilder("");
        boolean find;

        for(int i = 0; i<target.length(); i++)
        {
            stack.push(target.charAt(i));
            if(stack.size() >= blength)
            {
                find = true;
                for(int j = blength; j>0; j--)
                {
                    if(!stack.get(stack.size()-j).equals(bomb.charAt(bomb.length()-j)))
                    {
                        find = false;
                        break;
                    }
                }
                if(find)
                {
                    for(int j = 0; j<blength; j++)
                    {
                        stack.pop();
                    }
                }
            }
        }
        for(Character c : stack)
        {
            result.append(c);
        }

        System.out.println(result.length()!=0 ? result : "FRULA");
    }
}