9935번: 문자열 폭발

관련 사이트: https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

 

Stack을 이용하여 들어온 문자열 순서대로 비교하고 비교 완료된 문자열은 제거하는 형식으로 진행이 필요한 문제다.

아래와 같은 방법으로 문자를 비교하도록 한다.

 

1) 입력 받은 문자열의 첫번째 문자부터 마지막 문자까지 for문 수행

2) Stack에 문자 저장

3) Stack의 size >= 폭발 문자열의 길이? 조건을 만족한다면, 4) ~ 6)까지 수행

4) 폭발 문자열의 끝 문자부터 첫번째 문자까지 for문 수행

5) Stack의 top 부터 문자 비교 시, 폭발 문자열이 존재하는가 ? 조건을 만족한다면, 6) 수행

6) Stack에서 폭발 문자열 제거

 

다만, index를 통해 Stack 내의 값에 접근 가능한 Java와는 달리, C++의 경우 가장 위의 값만 알 수 있다.

때문에 5)와 같이 Stack 내의 문자와 폭발 문자열을 비교하기 위해서는 pop을 반복하고 일치하지 않는다면, 빼낸 문자들을 다시 push 하는 번거로운 과정이 필요해지게 된다.

 

따라서, Stack 대신 Stack의 역할을 해주는 배열을 사용하였다.

 

0) 문자 배열 생성, 사이즈 = 0

1) 입력 받은 문자열의 첫번째 문자부터 마지막 문자까지 for문 수행

2) 배열에 문자 저장 및 사이즈++

3) Stack의 size >= 폭발 문자열의 길이? 조건을 만족한다면, 4) ~ 6)까지 수행

4) 폭발 문자열의 끝 문자부터 첫번째 문자까지 for문 수행

5) Stack의 top 부터 문자 비교 시, 폭발 문자열이 존재하는가 ? 조건을 만족한다면, 6) 수행

6) 폭발 문자열 만큼 배열 사이즈 감소

 

#include <iostream>
using namespace std;

void printSt(char* st, int size)
{
    if (size == 0)
        cout << "FRULA\n";
    else
    {
        for (int idx = 0; idx < size; idx++)
            cout << st[idx];
        cout << "\n";
    }
}

int main()
{
    string str, bomb;
    cin >> str >> bomb;

    // 폭발 문자열을 포함할 수 없는 경우
    if (str.size() < bomb.size())
    {
        cout << str << "\n";
        return 0;
    }

    char st[str.size()];
    int size = 0;
    for (int i = 0; i < str.size(); i++)
    {
        // stack에 문자 저장
        st[size] = str[i];
        size++;

        if (size >= bomb.size())
        {
            // 끝에서부터 문자열 비교
            bool check = true;
            for (int cnt = 0; cnt < bomb.size(); cnt++)
            {
                // 문자열이 다른 경우
                if (bomb[bomb.size() - 1 - cnt] != st[size - 1 - cnt])
                {
                    check = false;
                    break;
                }
            }

            // 폭발 문자열이 있는 경우
            if (check)
                size -= bomb.size();
        }
    }

    printSt(st, size);
    return 0;
}

- 메모리: 4916 KB

- 시간: 72 ms

- 코드 길이: 1246 B

 

string이 아닌 char 배열을 통해 문제를 해결할 수도 있다.

배열의 고정 크기를 사용하므로 이 경우, 실제 문자가 들어있는 크기를 구해주기 위해서는 string.h 헤더를 추가해주고 strlen 함수를 사용해주도록 한다.

단, 이 때 설정해주는 고정 크기는 제시된 max 값보다 1 크게 설정해주도록 해야 한다.

 

#include <iostream>
#include <string.h>
using namespace std;

int main()
{
    char str[1000001];
    char bomb[37];
    cin >> str >> bomb;

    int str_size = strlen(str);
    int bomb_size = strlen(bomb);

    char result[str_size];
    int size = 0;
    bool check;
    for (int i = 0; i < str_size; i++)
    {
        // stack에 문자 저장
        result[size++] = str[i];

        if (size >= bomb_size)
        {
            // 끝에서부터 문자열 비교
            check = true;
            for (int cnt = 0; cnt < bomb_size; cnt++)
            {
                // 문자열이 다른 경우
                if (bomb[bomb_size - 1 - cnt] != result[size - 1 - cnt])
                {
                    check = false;
                    break;
                }
            }

            // 폭발 문자열이 있는 경우
            if (check)
                size -= bomb_size;
        }
    }

    // 문자열 출력
    if (size == 0)
        cout << "FRULA";
    else
        for (int idx = 0; idx < size; idx++)
            cout << result[idx];
    return 0;
}

- 메모리: 3852 KB

- 시간: 76 ms

- 코드 길이: 1092 B