Easy is Perfect

[백준] 9935번 C/C++ 풀이 _ 문자열 폭발

  • melonicedlatte
  • Dec 02, 2018


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

문자열 폭발 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 (언어별 추가 시간 없음)128 MB121272040136119.275%

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

  • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
  • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
  • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

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

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

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

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

예제 입력 1 

mirkovC4nizCC44
C4

예제 출력 1 

mirkovniz

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #5 3번

알고리즘 분류

풀이

이 문제의 분류는 '스택'입니다. 
스택을 사용한 제 풀이는 다음과 같습니다.

  • front, end 라는 스택을 만들어 놓고 end 스택에 글자의 끝부터 집어 넣습니다.
  • end를 하나씩 front로 넘기면서 그 글자가 '폭발 문자열'의 시작 문자열과 같은지 확인합니다.

  • 다른 경우에는 다음 end 에 있는 글자를 다시 '폭발 문자열'의 시작 문자열과 비교합니다.
  • 같은 경우에는 다음 end 에 있는 글자들도 폭발 문자열인지 순차적으로 확인합니다. 
  • 순차적으로 확인하면서는 '폭발 문자열'의 첫 글자와 같은 글자의 인덱스를 start_same에 넣습니다. 

  • 만약, 순차적으로 확인해서 폭발 문자열이 아니면 start_same 부터 탐색해야 되기 때문에 그 만큼 end로 넘깁니다.
  • 폭발문자열이면 해당 문자열만큼 제거해주고 이전에 폭발 문자열로 가능한 문자들이 있을 수 있기 때문에,
  • 최대 '폭발문자열 크기 -1' 만큼 end로 넘깁니다. 

이러한 풀이를 반복하는 것인데 소스코드를 확인해 보시는 것이 더 좋습니다. 

숏코딩은 stack 대신에 배열을 사용하여 제 풀이에서의 ('폭발 문자열의' 첫 글자와 같은 글자의 인덱스 만큼 넘기는 시간) 이 줄어듭니다. 
숏코딩도 코드를 통하여 확인해주세요~

스택을 사용한 소스코드

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
    stack<char> front, end;
    string str, bomb; cin >> str >> bomb;
    int bomb_size = bomb.size();
    int str_size = str.length();
    for (int idx = 0; idx < str_size; idx++)
        end.push(str[str_size - idx - 1]);
 
    int bomb_idx, start_same;
    bool is_find_bomb = false;
    while (!end.empty()) {
        bomb_idx = 0, start_same = 0;
        is_find_bomb = false;
        char now = end.top(); end.pop(); front.push(now);
        // 배열의 시작 단어와 다르면 다음 단어를 탐색한다. 
        if (now != bomb[bomb_idx++])    continue;
        
        // 배열의 시작단어와 나머지 단어들이 같은지 하나씩 빼서 확인한다. 
        while (!end.empty() && bomb_idx < bomb_size) {
            now = end.top(); end.pop(); front.push(now);
            // 첫 문자열과 동일한 문자열의 인덱스를 최초 1번 갱신한다.
            if (start_same == 0 && bomb[0])
                start_same = bomb_idx;
            // 폭발 문자열 인덱스와 현재 글자가 일치하면 다음 단계로 넘어간다. 
            if (now == bomb[bomb_idx]) bomb_idx++;
            else break;
        }
        
        // 폭발문자열이면 플래그 수정
        if (bomb_idx == bomb_size) is_find_bomb = true;
 
        // 폭탄을 찾았으면 폭탄 길이만큼 front에서 end으로
        if (is_find_bomb) {
            // bomb 길이만큼 front 에서 제거
            for (int idx = 0; idx < bomb_size; idx++)     front.pop();
            // 이전 문자열에서 정답 나올 수 있기 때문에 end로 다시 넣는다.
            for (int idx = 0; !front.empty() && idx < bomb_size - 1; idx++) {
                char now = front.top(); front.pop(); end.push(now);
            }
        } 
        else {
            // 더 이상 확인할 문자열이 없거나, 시작 문자와 동일한 문자가 없었으면 현재 위치부터 탐색
            if (end.empty() || start_same == 0) break;
            
            // 이전 문자열에서 정답 나올 수 있기 때문에 end로 다시 넣는다.
            for (int idx = 0; idx < bomb_idx + 1 - start_same; idx++) {
                char now = front.top(); front.pop(); end.push(now);
            }
        }
    }
    // 정답이 없으면 FRULA 를 출력
    if (front.empty()) {
        printf("FRULA"); return 0;
    }   
    // 뒤집기
    while (!front.empty()) {
        char now = front.top(); front.pop(); end.push(now);
    } 
    while (!end.empty()) {
        char now = end.top(); end.pop();
        printf("%c", now);
    }
    return 0;
}
cs

배열을 사용한 숏코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <string.h>
int t_len, p_len, pos;
char text[1000010], pattern[40], ans[1000010];
 
bool is_matching(int start) {
    for (int i = start; i < start + p_len; ++i) 
        if (ans[i] != pattern[i - start]) 
            return false;
    return true;
}
 
int main() {
    scanf("%s%s", text, pattern);
    t_len = (int)strlen(text);
    p_len = (int)strlen(pattern);
    for (int t_idx = 0; t_idx < t_len; ++t_idx) {
        ans[pos++] = text[t_idx];
        if (pos - p_len >= 0 && is_matching(pos - p_len))
            pos -= p_len;
    }
    ans[pos] = '\0';
    printf("%s\n", pos ? ans : "FRULA");
}
cs



Search