[백준/JAVA] 9935번: 문자열 폭발

📖 문제

9935번: 문자열 폭발

 

 

💡  풀이 방식

• 스택

스택을 만들어 폭발 문자열과 일치하는 문자열이 생겼을 때 바로바로 빼주는 식으로 push와 pop연산을 진행한다.

 

1. 문자열 str의 전체 길이를 탐색하며 스택에 문자를 하나씩 저장(push)한다.

2. 스택에 들어간 문자의 길이가 폭발 문자열의 길이보다 길다면, 폭발 문자열이 있는지 탐색한다. (⚠ 탐색 범위 : stack.size() - bomb.length() ~ stack.size())

  - 폭발 문자열과 일치하지 않는다면 break;

  - 일치하는 문자열이 존재한다면, stack.pop()

 

 

 

💥 유의사항

- 문자열의 최대 길이가 100만이므로 시간 초과, 메모리 초과에 주의하자.. (🚫 O(N^2) )

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
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<Character> stack = new Stack<>();
           
        for(int i = 0 ; i < str.length() ; i++) {
            stack.push(str.charAt(i));
            
            // 스택 크기와 폭발 문자열과 길이가 같아질 때 탐색 시작
            if(stack.size() >= bomb.length()) {
                boolean isSame = true; // 폭발 문자열이 있는지 확인용 변수
                
                for(int j = 0 ; j < bomb.length() ; j++) {
                    char ch1 = stack.get(stack.size() - bomb.length() + j); // 폭발 문자열의 길이만큼 꺼내 저장
                    char ch2 = bomb.charAt(j);
                    
                    if(ch1 != ch2) {
                        isSame = false;
                        break;
                    }
                }
                
                if(isSame) { // 일치하는 문자열이 존재하는 경우, 폭발 문자열 삭제
                    for(int j = 0 ; j < bomb.length() ; j++)
                        stack.pop();
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(char ch : stack)
            sb.append(ch);
        
        System.out.println(sb.length() == 0 ? "FRULA" : sb.toString());
    }
}
 

 

 

➕ 다른 풀이 방식

- 같은지 확인할 때 boolean 변수 안 쓰고 활용하신 풀이

[Java] 백준 9935번 [문자열 폭발] 자바

 

 

- 스택 안 쓰시고, StringBuilder만 활용하시는 풀이...! 심지어 더 빠르다. (sb.delete())

[백준] 9935번 문자열 폭발 (자바 풀이)

---

💦 어려웠던 점

- 처음에 replaceAll로 해서 처리하려다가 문자열의 최대 길이가 100만이므로 메모리 초과가 떴었다.

 

자바의 String은 immutable한 값이라 값을 바꿀 때마다 매번 새 String을 할당해야 하기 때문이라고 한다.(참고1, 참고2)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

import java.util.*; import java.io.*;   public class Main {     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                  String str = br.readLine();         String bombStr = br.readLine();                  while(str.contains(bombStr)) {             str = str.replaceAll(bombStr, "");    // 시간 복잡도 : O(N^2)         }                  System.out.println(str.length() == 0 ? "FRULA" : str);     } }   Colored by Color Scripter

cs

 

 

 

🧐 새로 알게 된 내용

스택은 List  인터페이스를 상속받은 구현 클래스로, 스택 객체를 생성해도 ArrayList 메소드를 사용할 수 있다.

그래서 List 인터페이스에서 사용하는 .get 메소드를 사용한 거구나!!

그 외 사용 가능한 메소드들은 아래와 같다.

 

- 스택.get(인덱스) / 스택.elementAt(인덱스) : ArrayList의 .get 메소드는 주어진 idx에 저장된 값을 반환

- 스택.set(인덱스, 값) : 인덱스 위치에 있는 스택 값 변경하기

- 스택.indexOf("값") : 스택 특정 값이 어느 인덱스에 있나 확인

 

 

아 자료구조 좀만 생각해도 저렇게 메소드를 쓸 생각을 할 수 있었는데..  잊고 있었다,,,

이래서 자료구조가 중요한,,,

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[BOJ] 백준 9935번 문자열 폭발 (Java)

[BOJ][Java] 백준 9935번: 문자열 폭발

 

[백준] G4 9935번 문자열 폭발 (JAVA)

 

 

✔ 스택 관련 참고

(특히 첫 번째 글이 최고,,,)

[JAVA] Stack 직접 구현하기

자바 Stack 예제부터 사용방법까지

[자료 구조] 스택 (Stack)