백준 3111 검열 Java

스택을 활용해서 풀어야 하는 문제인 검열이다.

 

총 23번의 시도 끝에 성공할 만큼 고생을 많이 한 문제였다.

이 문제에서 고생하는 이유는 대부분 출력 초과, 시간 초과였는데

나는 메모리 초과 때문에 고생을 많이 했다.

텍스트의 최대길이가 300,000이기 때문에 스택을 활용하지 않고

일일이 검사하는 방법은 O(n^2)으로 당연히 시간 초과이다.

출력 초과는 내 생각에 그냥 틀렸다는 말과 똑같은 것 같다.

 

우선 문제를 푸는 방법을 설명하면

1. 왼쪽 스택, 오른쪽 스택 총 2개의 스택을 만든다.

2. 왼쪽에서부터 텍스트를 훑으면서 왼쪽 스택에 넣고 key값을 발견하면 왼쪽 스택에서 지운다.

3. 오른쪽에서부터 텍스트를 훑으면서 오른쪽 스택에 넣고 key값을 발견하면 오른쪽 스택에서 지운다.

4. 텍스트를 전부 훑었으면 왼쪽 스택에 있는 것을 오른쪽 스택으로 옮긴다.

5. 다 옮겨진 오른쪽 스택에서 다시 key값이 있다면 지운다.

 

주의해야 할 점은 다 옮겨진 오른쪽 스택에서 key값을 한번 지운다고 해서 정답이 아니다.

key값을 지움으로써 다시 새로운 key값이 생길 수 있기 때문에

key값이 완전히 없어질 때까지 반복해서 key값을 찾아 지워야 한다.

 

그리고 스택에서는 peek()와 pop() 밖에 몰랐었기 때문에

어떻게 스택에 들어있는 값이 key값과 일치하는지 확인할까를 고민했는데

스택에도 .get(int index) 메소드가 있다는 것을 처음 알았다.

 

때문에 왼쪽에서 지우고, 오른쪽에서 지우는 과정은

스택에 넣은 마지막 문자가 key값의 마지막 문자열과 같으면

get 메소드를 활용해서 key값과 일치하는지 확인하고

일치한다면 key의 길이만큼 pop 해주었다.

오른쪽에서부터 확인할 때는 오른쪽 스택에 텍스트의 문자가 거꾸로 들어가기 때문에

key값도 거꾸로 해서 확인해야 한다.

 

마지막에 오른쪽으로 다 옮기고 새로 만들어진 key값을 계속해서 지우는 과정은

StringBuilder클래스의 indexOf메소드와 delete메소드를 활용했다.

 

재귀 호출을 한 것도 아니고, 크기가 큰 배열을 선언한 것도 아닌데 계속해서 메모리 초과가 나서

왜인지 정말 오랜 시간을 고민하다 백준에 질문을 올리고 그 해답을 찾을 수 있었다.

 

오른쪽 스택에 옮기고 StringBuilder를 통해 key값을 계속해서 지우는 과정이다.

이 과정에서 메모리 초과가 났을 거라곤 생각을 못했었다.

어느 부분에서 메모리 초과가 발생했는지는 내가 올린 질문의 답변을 통해 확인하자.

 

String에 + 연산을 하는 과정에서 메모리 초과가 발생했던 것이다.

String클래스는 immutable클래스로 수정이 불가능하지만

+연산을 한다면 그냥 새로운 String변수를 만들어서 간단하게 붙이는 줄 알았다.

말 그대로 더하기이기 때문에 간단할 줄 알았던 게 메모리 초과 발생의 원인이었다.

 

내가 작성한 코드의 String 더하기 연산은 위에 답변에서도 확인할 수 있듯이

ans = new StringBuilder(ans)).append(ans).toString(); 코드로 바뀌어서 

수많은 가비지를 생성하고 있었던 것이었다.

 

답변대로 수정하였더니 바로 성공하였다.

 

import java.util.Scanner;
import java.util.Stack;
 
public class Q3111 {
    public static void main(String[] args)  {
        Scanner scan = new Scanner(System.in);
        String key = scan.next();
        String text = scan.next();
        Stack<Character> left = new Stack<>();
        Stack<Character> right = new Stack<>();
        int start = 0;
        int end = text.length()-1;
        boolean isRemove = false;
 
        while(start <= end) {
 
            if(!isRemove) {
                left.push(text.charAt(start++));
                if(left.size() >= key.length() && left.peek() == key.charAt(key.length()-1)) {
                    int keyLen = key.length()-1;
                    boolean check = true;
                    for(int j=left.size()-1; j>=left.size()-key.length(); j--) {
                        if(left.get(j) != key.charAt(keyLen--)) {
                            check = false;
                            break;
                        }
                    }
                    if(check) {
                        isRemove = true;
                        for(int j=0; j<key.length(); j++) {
                            left.pop();
                        }
 
                    }
                }
            }
            if(isRemove && start <= end) {
                String keyRev = new StringBuilder(key).reverse().toString();
                right.push(text.charAt(end--));
                if(right.size() >= key.length() && right.peek() == keyRev.charAt(key.length()-1)) {
                    int keyLen = key.length()-1;
                    boolean check = true;
                    for(int j=right.size()-1; j>=right.size()-key.length(); j--) {
                        if(right.get(j) != keyRev.charAt(keyLen--)) {
                            check = false;
                            break;
                        }
                    }
                    if(check) {
                        for(int j=0; j<key.length(); j++) {
                            right.pop();
                        }
                        isRemove = false;
                    }
 
                }
            }
 
        }
        int leftSize = left.size();
        for(int i=0; i<leftSize; i++) {
            right.push(left.pop());
        }
        StringBuilder sb = new StringBuilder();
        while(!right.isEmpty()) {
            sb.append(right.pop());
        }
        while(true) {
            int idx = sb.indexOf(key);
            if(idx < 0) break;
            sb.delete(idx, idx+key.length());
        }
        System.out.println(sb.toString());
    }
}