[백준 9935번 문자열 폭발]

728x90

오늘의 문제는  "문자열 폭발"이다.

 

#고민의 흐름

처음엔 무조건 완전탐색!

 

처음엔 코드를 어떻게 짜야하나 고민하다가 큐를 두 개 만들어서

큐 1 > 큐2, 큐2 > 큐1 번갈아 가며 폭발 문자열을 제거해 나가는 방식을 채택했다.

 

하지만 결과는 메모리 초과 ,, 100만이나 되는 길이의 문자열을 하나하나 다 넣어주니

어떻게 보면 당연한 결과였던 것 같다.

 

한참을 고민하다가 아래의 분류(힌트)를 보았다...

안 보고 충분한 시간을 고민해 보는 연습도 해야 하는데.. ㅠ

 

그 결과 자료구조의 스택!으로 분류되어 있음을 알게 되었다.

하지만 스택임을 알고 나서도 잠시 고민을 하게 되었다.

어... 스택? 왜..?

 

그래도 결국 방법을 찾은 거 같아 그대로 문제를 풀이하니 맞았다.

자세한 내용은 코드와 함께 보자!

 

코드는 다음과 같다.

( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )

( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )

 

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 boom = br.readLine();
        Stack<Character> s = new Stack<>(); // 스택과 입력 받아주기 !
        for(int i = 0; i<str.length(); i++){ // 기본 str의 길이만큼 돌면서 ~
            char c = str.charAt(i); // 이번 문자
            if(c != boom.charAt(boom.length()-1)){ // 폭탄문자열의 마지막이랑 다르다면?
                s.add(c); // 스택에 넣어준다.
            }else{ // 마지막과 같다면?
                if(s.size() + 1 < boom.length()){ 
                // 하지만 같더라도 이미 스택안의 내용합쳐도 길이가 부족하다면
                // 곱게스택에 마저 넣어놓고 이어서 진행한다.
                    s.add(c);
                    continue;
                }
                
                // 충분히 검사해볼만한 크기라면?!
                String temp = String.valueOf(c);
                for(int j = 0; j<boom.length()-1; j++){
                    temp = String.valueOf(s.pop()) + temp;
                }
                //폭파 문자열과 같은 길이만큼 꺼내며 문자열을 만들고
                
                //만들어진 문자열이 폭파 문자열과 같은지 확인하고!
                if(!temp.equals(boom)){ // 다르다면 다시 그대로 스택에 넣기
                    for(int j = 0; j<temp.length(); j++){
                        s.add(temp.charAt(j));
                    }
                }
                
                //같다면 내비두고 진행하기 !
                //temp의 초기화는 매번 해주니까 신경안써도되고
                //내비두고 진행하면 자연스레 그만큼 빠진다 !
            }
        }

        if(s.size() == 0){ // 다하고 보니 스택이 비었다면?
            System.out.print("FRULA"); // 해당하는 문자열 출력하고 끝내기 !
            return;
        }

        StringBuilder sb = new StringBuilder();
        while(!s.isEmpty()){ // 스택에 남은게 있다면? 싹다 sb에 넣어주고
            sb.append(s.pop());
        }
        System.out.print(sb.reverse()); // 출력하기전에 뒤집는거 잊지말기 !
    }
}

 

 

 

요즘 시간에 쫓겨 하루 한 문제를 풀다가도 고민하는 시간이 점점 줄어가고 있다.

아침시간을 좀 더 잘 활용할 수 있도록 일찍 일어나야 하는데 ,, 쉽지가 않다..자기소개서도 작성해야 하고 사이드 프로젝트도 해야 하는데 ,, 파이팅 해야겠다..

궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~

 

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