뚝딱뚝딱

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

💡 문자열 폭발

이 문제를 풀다가 내가 폭발하는 줄 알았다.

2시간동안 총 16번의 시도끝에 결국 해냈다.

세번의 서로 다른 시도가 있었다.

[첫번째 시도]. 자바의 String에서 제공하는 contains함수를 이용하는 것이다.

입력받은 전체 문자열에서 target문자열이 있는지를 contains()함수를 이용하였고, String의 replace함수를 사용해 target을 ""빈 문자열로 변경하도록 하였다.

뭐야 너무 간단하잖아? 하고 자신있게 제출했는데... 예상과는 다르게, "메모리 초과"라는 결과가 나왔다.

String의 경우 문자열이 const이기 때문에, 내용이 바뀌면 계속해서 새로운 문자열을 만들어 저장한다.

이 부분을 완전히 간과하고 있었던 것이다..

그래서 최대 100만 길이 문자열이라면, 굉장히 많은 메모리를 낭비하게 될 것이다.

따라서 String의 replace함수로는 해결할 수 없다!

[두번째 시도]. StringBuilder 클래스를 사용하였다

앞 시도에서 문자열이 계속해서 새로 생성되니까, 메모리 초과가 되는 걸 보고, 덧셈연산을 하지 않고 메모리 효율적인 StringBuilder를 사용하면 되겠다!! 싶어서 StringBuilder객체 sb를 생성하고 문자열을 저장해 주었다.

그리고 sb에서 indexOf()함수를 사용해서 target이 존재하는 위치를 찾고, delete함수를 통해 target을 지우도록 하였다.

그리고 sb를 toString함수를 통해 string으로 출력하도록 하였다.

이젠 되겠지..?? 했는데... 이번에 "시간초과"라는 결과가 나왔다. 

따라서 StringBuilder는 단순히 문자열을 받는 입장으로는 사용할 수 있겠구나라고 판단하였다!

[세번째 시도].

결국은 한번씩 순회를 하는 수밖에 없겠다는 생각을 하였고... 

결론적으로 스택을 활용하면 되는 문제였다!

다음 과정을 거친다.

• 문자열 길이만큼 순회하면서, 스택의 길이가 target 문자열길이 이상이면 끝에서부터 target길이만큼 비교 후, 동일하면 target길이 만큼 pop한다.
• 문자열 덧셈 연산을 안하기 위해 StringBuilder를 사용하고, stack에 있는 값을 그대로 옮겨준다.
• stringBuilder의 크기가 0이 아니면, toStirng으로 출력하도록 하고, 0이면 요구사항에 있는 문자열을 출력한다.

이렇게 하면, 딱 n번 순회하니 시간 초과 문제도 없고, 스택을 통해 push pop으로 문자열을 조정함으로써 새로운 문자열이 생기는 등 메모리 낭비가 발생하지 않을 수 있다.

전체 코드는 아래와같다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      String st=scanner.nextLine();
      String target=scanner.nextLine();
      scanner.close();
      
      Stack<Character> stack = new Stack<>();
     
      for(int i=0; i<st.length(); i++){
          stack.push(st.charAt(i));
          
          if(stack.size()>=target.length()){
              boolean flag = true;
              
              for(int j=0; j<target.length(); j++){
                  if(stack.get(stack.size()-target.length()+j)!=target.charAt(j)){
                      flag=false;
                      break;
                  }
              }
              if(flag){
                  for(int j=0; j<target.length(); j++){
                      stack.pop();
                  }
              }
          }
      }
      
      StringBuilder sb = new StringBuilder();
      
      for(Character c : stack){
          sb.append(c);
      }
      
      if(sb.length()!=0){
        System.out.print(sb.toString());
      }
      else System.out.print("FRULA");
    }
}

헷갈렷던 자바 개념은, stack에 있는 값을 sb에 옮기는 과정이었는데

stack을 뒤에서 부터 뺄 수 있다는 것과, 새로운 값을 sb에 넣을 때는 오른쪽 방향으로 넣는다는 생각때문에,

문자열이 뒤집어져서 sb에 들어가지 않을까? 했는데..

결론적으로 sb에 들어갈 때는 스택의 맨 뒤의 값을 넣고, 다음 값을 넣을 때 앞 방향으로 누적되도록 들어갈 수 있기 때문에, 결국 stack에 들어간 순으로 sb에도 누적할 수 있다고 한다.

알고나면 쉬운데, 생각해내기가 어려웠던 문제였다!