본문 바로가기
백준

[백준] 알고리즘 분류(문자열,JAVA)9935번, 문자열 폭발

by 열정적인 이찬형 2022. 9. 23.

문제 링크

 

9935번: 문자열 폭발

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모

www.acmicpc.net


주의사항

  • JAVA를 사용하여 프로그램을 사용하였습니다.
  • 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{ 	
	public static void main(String[] args){
    }
}

문제 설명


접근 방법

이 문제에 핵심

 

1. 폭발 문자열에는 같은 문자를 2개 이상 포함하지 않는다.

2. 폭발 문자열이 되면 폭발한 뒤 남은 문자열을 붙입니다.

3. 모든 폭발이 끝난 뒤 문자열에 아무것도 문자가 남지 않으면 "FRULA"을 결과로 출력합니다.

 

문제를 처음 접근할 때 시간복잡도만 집중하여 HashMapStack을 사용하여서 폭발이 진행되고 붙일 때에도 바로 폭발 문자열이 만들어지는지 확인하도록 처음에 구현하였지만 메모리 초과로 실패하였습니다.

 

그래서 단순하게 접근을 하면서 문자열에 각 글자가 폭발 문자열에 마지막 글자와 동일할 때 이전에 글자들을 탐색하여 폭발 문자열인지 확인하고 폭발 문자열이면 폭발하도록 하였습니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 문자열에서 폭발 문자열에 해당하는 곳을 폭발시킨 뒤 붙이는 작업을 반복합니다.

 

3. 폭발이 종료된 뒤 문자열의 상태에 따라 결과를 출력합니다.

 

폭발

 

문자열에 글자들을 순차적으로 쌓아놓기 위해서 Stack(LIFO)을 이용하였습니다.

 

문자열에서 폭발 문자열이 마지막 글자와 동일한 곳까지 Stack에 저장합니다.

 

Ex)

문자열 : 112ab2

폭발 문자열 : 12ab

마지막 폭발 글자 : b

 

마지막 폭발 글자와 동일한 곳까지 Stack에 저장!

b(5)
a(4)
2(3)
1(2)
1(1)

 

폭발 문자열인지 탐색!

 

탐색 범위

2 ≤ n ≤ 5 (Stack크기 - 폭발 문자열 길이 ≤ n ≤ Stack 크기)

= 12ab

 

폭발 문자열로 성립! 폭발!

1(1)

 

이후 문자열 다시 탐색!

2(2)
1(1)

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

문자열 : mirkovC4nizCC44

폭발 문자열 : C4

 

2. 문자열에서 폭발 문자열에 해당하는 곳을 폭발시킨 뒤 붙이는 작업을 반복합니다.

 

mirkovC4nizCC44

 

폭발 문자열 마지막 글자인 곳까지 탐색!

4(8)
C(7)
v(6)
o(5)
k(4)
r(3)
i(2)
m(1)

폭발 문자열인지 탐색!

2 ≤ n ≤ 5

= C4

폭발!

v(6)
o(5)
k(4)
r(3)
i(2)
m(1)

다시 탐색!

4(12)
C(11)
C(10)
z(9)
i(8)
n(7)
v(6)
o(5)
k(4)
r(3)
i(2)
m(1)

폭발 문자열인지 탐색!

11 ≤ n ≤ 12

= C4

폭발!

C(10)
z(9)
i(8)
n(7)
v(6)
o(5)
k(4)
r(3)
i(2)
m(1)

다시 탐색!

4(11)
C(10)
z(9)
i(8)
n(7)
v(6)
o(5)
k(4)
r(3)
i(2)
m(1)

폭발 문자열인지 탐색!

10 ≤ n ≤ 11

= C4

폭발!

z(9)
i(8)
n(7)
v(6)
o(5)
k(4)
r(3)
i(2)
m(1)

폭발 종료!

 

3. 폭발이 종료된 뒤 문자열의 상태에 따라 결과를 출력합니다.

 

Stack이 비어있으면 모두 폭발된 것이지만 남아있기 때문에 Stack에 저장된 정보를 출력합니다.

 

mirkovniz을 결과로 출력합니다.

 

 

  • BufferedReader를 사용하여 입력되는 정보를 저장합니다.
  • 문자열을 탐색하여 폭발 문자열이 존재하는지 확인합니다.
  • 폭발 문자열이면 폭발을 진행시키는 것을 반복합니다.
  • 폭발이 모두 종료 된 뒤 현재 문자열에 따라 결과를 BufferedWriter 저장하였습니다.
  • BufferedWriter에 저장된 결과값을 출력하였습니다.

※문자열이 폭발 문자열보다 길이가 작으면 절대 폭발이 일어나지 않기 때문에 입력된 문자열을 그대로 출력합니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 저장하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Character> stack = new Stack<>();	//글자 저장할 Stack
        String input = br.readLine();	//문자열
        String word = br.readLine();	//폭발 문자열
        //문자열이 폭발 문자열보다 길이가 작으면 폭발할 일이 없습니다.
        if (word.length() > input.length()) {
            bw.write(input);
        } else {
            //문자열 탐색
            for (int i = 0; i < input.length(); i++) {
                stack.add(input.charAt(i));
                //글자가 폭발 문자열에 마지막 글자인지 확인
                if (stack.size() >= word.length() && stack.peek() == word.charAt(word.length()-1)) {
                    boolean check = false;
                    //폭발 문자열인지 확인
                    for (int j = 0; j < word.length(); j++) {
                        if (stack.get(stack.size() - word.length() + j) != word.charAt(j)) {
                            check = true;
                            break;
                        }
                    }
                    //폭발 문자열일 때 Stack에 저장된 정보 폭발시키기
                    if (!check) {
                        for (int j = 0; j < word.length(); j++)
                            stack.pop();
                    }
                }
            }
            //Stack에 저장된 정보 저장
            StringBuilder answer = new StringBuilder();
            for(Character c : stack)
                answer.append(c);

            //문자열이 폭발된 후에도 남아있을 경우
            if(answer.length()>0)
                bw.write(answer.toString());
            else		//문자열이 모두 폭발 되었을 때
                bw.write("FRULA");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}
 

댓글