[9935] - 문자열 폭발

 

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

9935번: 문자열 폭발

 

C# 출력이 느린걸 너무 간과했다..

 

틀린 이유

1. 메모리 초과, 틀렸습니다 -> 문제를 잘못 읽고 폭탄문자열에 해당하는 문자가 있으면 해당 문자 삭제 ex) C4 면 C와 4 삭제

2. 시간초과 -> 겨우 stringbuilder 사용안해서 틀림..

 

접근 방식

- 스택은 먼저 들어온것이 늦게 나오므로 문자열을 뒤에서 부터 넣어주면 pop할 때 정순으로 나와서 뒤부터 시작.

- 뒤에부터 시작했으니 폭탄의 앞글자가 나오면 폭탄의 길이만큼 비교, 폭탄이면 그대로 빼고 아니면 다시 뒤부터 넣어줌

- 출력

• 시간초과 때문에 string에서 list, char[]로 자료형도 바꿔보고, 폭탄의 글자 전부를 뺀 후 비교해서 구현도 해보았지만, 결국 입출력이 느린 C#에서 stringbuilder를 안써서 계속 틀린문제..

 

list 사용해서 폭탄인지 하나하나 구별한 것

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Baekjoon.Gold
{
    class _9935
    {
        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            string str = Console.ReadLine();
            string bomb = Console.ReadLine(); //폭탄 문자열

            Stack<char> stack = new Stack<char>();

            //스택은 선입후출이니 뒤에서부터 해줌
            for(int i = str.Length-1; i>=0; i--)
            {
                stack.Push(str[i]);
                //스택의 크기가 폭탄 이상이고
                if (stack.Count >= bomb.Length)
                {
                	//가장최근에 들어온게 폭탄의 앞글자면
                    if(stack.Peek() == bomb[0])
                    {
                    	//폭탄인지 구별하기
                        bool isbomb = true;
                        List<char> check = new List<char>();
                        for(int j = 0; j<bomb.Length; j++)
                        {
                            check.Add(stack.Pop());
                            if (check[j] != bomb[j])
                            {
                                isbomb = false;
                                break;
                            }
                        }

                        if (!isbomb)
                        {
                            for(int j = check.Count-1; j>=0; j--)
                                stack.Push(check[j]);
                        }
                    }
                }
            }

            if (stack.Count > 0)
                while (stack.Count > 0)
                    stb.Append(stack.Pop());
            else
                stb.AppendLine("FRULA");

            Console.WriteLine(stb);
        }
    }
}

 

폭탄길이만큼 출력 후 한번에 비교한 것

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Baekjoon.Gold
{
    class _9935
    {
        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            string str = Console.ReadLine();
            string bomb = Console.ReadLine(); //폭탄 문자열

            Stack<char> stack = new Stack<char>();

            for(int i = str.Length-1; i>=0; i--)
            {
                stack.Push(str[i]);
                if (stack.Count >= bomb.Length)
                {
                    if(stack.Peek() == bomb[0])
                    {
                        string check = "";
                        for (int j = 0; j < bomb.Length; j++)
                            check += stack.Pop();

                        if (check != bomb)
                        {
                            for(int j = check.Length-1; j>=0; j--)
                                stack.Push(check[j]);
                        }
                    }
                }
            }

            if (stack.Count > 0)
                while (stack.Count > 0)
                    stb.Append(stack.Pop());
            else
                stb.AppendLine("FRULA");

            Console.WriteLine(stb);
        }
    }
}