백준/9935 문자열 폭발

작성일 | In

< 문제 분석 및 풀이 방법 >

Backjoon :: 문자열 폭발 문제는 스택을 활용하는 문제다.

  • Stack 클래스를 사용할 필요 없이 배열을 스택처럼 사용하면 된다.
  • 입력받는 문자열을 전부 char 배열로 변환해 체크했다.
  • 입력받는 문자열 : target
  • 찾아야 하는 문자열 : find
  • 옮기는 char 배열 : stack
  1. 현재 stack 배열 idx가 find 길이보다 작다면 stack 배열에 target[idx] 문자를 추가한다.
  2. 1번에 해당되지 않고 find 마지막 문자와 다르면 stack 배열에 target[idx] 문자를 추가한다.
  3. 1,2번에 해당하지 않고 find 마지막 문자와 target[idx]의 문자가 같으면 find 배열 길이만큼 for문을 돌면서 일치 여부를 확인한다.
    1. 만약 일치한다면 idx를 현재 위치로 옮긴다.(덮어 씌우니까 따로 지울 필요는 없다)
    2. 만약 일치하지 않는다면 stack 배열에 target[idx] 문자를 추가한다.

< 소스 코드 >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.io.*;
import java.util.*;

public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] target = br.readLine().toCharArray();
        char[] find = br.readLine().toCharArray();
        char[] stack = new char[target.length];
        int idx = 0;
        for (int i = 0; i < target.length; i++) {
            stack[idx++] = target[i];
            if (idx < find.length) continue;            //찾아야 하는 문자열 길이보다 작으면 계속 옮긴다
            if (target[i] == find[find.length - 1]) {   //찾아야 하는 문자열 끝과 옮긴 문자가 같다면
                boolean flag = false;
                for (int j = 0; j <= find.length - 1; j++) {        //일치여부 확인
                    if (stack[idx - find.length + j] != find[j]) flag = true;
                }
                if (!flag) {        //일치하면 idx 앞으로 이동
                    idx = idx - find.length;
                }
            }
        }
        if (idx == 0) System.out.println("FRULA");
        else {
            for (int i = 0; i < idx; i++) {
                sb.append(stack[i]);
            }
            System.out.println(sb);
        }
    }
}