[9935번] 문자열 폭발

문제 출처 :

 

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 스택의 활용

2. 문자 처리

이 문제는 처음 보면 strstr처럼 문자열 검색으로 코딩을 짜 볼 수 있다.

하지만, 그렇게 짠다면 문자열의 위치가 계속 변하고, ( cc44처럼 다시 이전으로 돌아가야될 상황들이 발생 ) 이렇게 계속 진행되다보면

시간 복잡도에서 밀릴 수 있다.  

따라서 스택을 이용하여 코드를 완성한다.

스택의 설명은 다음과 같다.

S :: 처음 스택에 push될 스택이며, 값을 조사할 때 이용된다.

S2 :: 정답을 비교할때 잠시 넣어두는 임시 스택이다.

String :: 최종 정답을 출력할 때 이용하는 스택이다.

이 코드는 주석을 풀어 실행 해 본다면 이해가 쉬울 것이다.

#include <iostream>
#include <stack>
#include <string.h>
 
using namespace std;
 
char arr[1000001];
 
 
int main()
{
    stack <char> S;
    stack <char> S2;
    stack <char> String;
 
    char ans[40];
 
    scanf("%s", arr);
    scanf("%s", ans);
 
    int len = strlen(arr);
    int len2 = strlen(ans);
    int tmp = len2 - 1;
    int success = 0;
 
    for (int i = 0; i < len; i++)
    {
        S.push(arr[i]);
        while (S.empty() != 1)
        {
            if (S.top() == ans[tmp] && S.size() >= tmp)
            {
                S2.push(S.top());
                // cout <<  " 스택 값 넣는중 :: " << S.top() << endl;
                S.pop();
                tmp--;
 
                success++;
                if (tmp == -1 && S2.size() == len2)
                {
                    while (S2.empty() != 1)
                    {
                        // cout << "임시 스택초기화 :: " << S2.top() << endl;
                        S2.pop();
                    }
                    tmp = len2 - 1;
                }                
            }
 
            else
            {
                while (success != 0 && S2.empty() != 1)
                {
                    // cout << "다시 스택에 push :: "  << S2.top()  << endl;
                    S.push(S2.top());
                    S2.pop();
                    success--;
                }
                tmp = len2 - 1;
                break;
            }
 
        }
 
        while (S2.empty() != 1)
        {
            //cout << "처리되지 못한 값 push :: " << S2.top() << endl;
            S.push(S2.top());
            S2.pop();
            tmp = len2 - 1;
        }
 
 
 
    }
 
    // 스택에 남은것이 없을 때 출력
    if (S.empty() == 1)
        cout << "FRULA";
 
    // 스택에 남아있을 때 정답 출력을 위해 스택 뒤집어 담는 과정
    while (S.empty() != 1)
    {
        String.push(S.top());
        S.pop();
    }
 
    // 정답이 담긴 스택 출력
    while (String.empty() != 1)
    {
        cout << String.top();
        String.pop();
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>