백준 9935번: 문자열 폭발 (java)

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

9935번: 문자열 폭발

문제

난이도 : 골드 4

유형 : 문자열, 스택 

 

몇년만에 알고리즘 한문제를 풀어봤는데 문제부터 이해를 잘 못했다.

처음문제를 보곤 ABCD 라는 원문에 폭발문자열이 AC 면은 출력으로 BD 가 나오는것으로 이해하고 풀이했고

당연히 통과 될리가 없었다.

 

문제를 이해하지 못한거 같아 검색하여 다른분의 구상을 보니 애초에 문제를 잘못이해했단걸 알았고 

이미 다른사람의 풀이 구상을 읽어버려서 그 흐름대로 짜게됐다

사고흐름

1. 사실 stack 이 아니라 queue 를 써도 구현은 똑같이 가능할 것 하지만 다른사람 글을 봐버려서 stack으로 사고..

2. 입력받은 문자열을 하나씩 stack에 push 하면서 폭발 문자열 길이와 같거나 큰지 비교한다

3. 조건에 해당하면 stack.size-폭발문자 사이즈   ~ stack.size 끝 까지 폭발문자열과 비교한다.

    3-1. 이때 폭발문자열 패턴과 맞지않으면 flag = false로 변경 -> 추후 break 추가

    3-2. 모두 일치하면 flag=ture 인 상태이므로 해당 길이의 문자를 pop 한다.

 

풀이

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String  inputText = sc.next();
        String  inputBomb = sc.next();
        int bombleng =inputBomb.length();

        char[] OriginArray =inputText.toCharArray();
        char[] OriginBomb = inputBomb.toCharArray();

        Stack originStack = new Stack();

        for(int i =0; i < inputText.length(); i++) {
            originStack.push(OriginArray[i]);
            boolean flag = true; //탐색전 true 초기화

            //탐색문자와 bomb 문자 같아지면 탐색 시작
            if(originStack.size() >= bombleng){
                for(int j = 0; j <bombleng; j++ ){
                    if(!originStack.get(originStack.size()-bombleng +j).equals(OriginBomb[j])){
                        flag = false;
                    }
                }
                if(flag){ //플래그 걸린거 하나도없으면 문자열폭발
                    for(int popindex = 0; popindex<bombleng; popindex++){
                        originStack.pop();
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(Object c : originStack){
            sb.append(c);
        }
        if(originStack.size() == 0){
            System.out.println("FRULA");
        }else{
            System.out.println(sb);
        }
    }
}

아래와 같이 실행시간이 두배나 차이가 난다.

가장 큰 원인은 flag = false 가 나왓으면 더 이상 탐색할 필요가 없기에 break를 해주는것이 올바르다.

 

내 풀이

 

그대로 카피한 풀이

 

 

-참조글

https://loosie.tistory.com/317