백준알고리즘 9935번 문자열 폭발 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 9935
• 문제명: 문자열 폭발
• 언어: C#
• 분류: 자료 구조, 문자열, 스택
• 비고: 

 

문제

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

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

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

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

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

 

입력

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

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

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

 

출력

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

 

풀이

StringBuilder를 사용해 문자열 조합 시 새로운 변수 생성을 안 해도 결합 가능하다. 사용하는 함수들을 첨부했다.

Append(): 문자열을 StringBuilder 객체 끝에 추가

AppendLine(): Append와 동일하나 한 줄을 띄운다. 엔터 키도 눌렀다고 생각하면 된다.

Stack이라는 자료 구조를 사용한다. 밑에는 Stack에서 사용하는 함수들을 작성했다.

Push(): 개체를 Stack 맨 위에 삽입한다.

Peek(): Stack 맨 위의 개체를 제거 없이 반환한다.

Pop(): Stack 맨 위의 개체를 제거한다. 제거된 개체는 반환된다.

using System.Text;

// 스트링빌더 선언
StringBuilder sb = new StringBuilder();
// 문장 입력을 받아 저장
string sentense = Console.ReadLine();
// 문장에서 제거할 요소 입력받아 저장
string explosive = Console.ReadLine();
// 문자를 저장할 스택 선언
Stack<char> stack = new Stack<char>();

// 스택은 후입선출이므로 역순으로 출력한다
for (int i = sentense.Length - 1; i >= 0; i--)
{
    // 스택에 sentense의 문자들을 역순으로 삽입한다.
    stack.Push(sentense[i]);

    // 스택에 남아있는 항목의 수가 제거 요소의 길이보다 더 길 경우
    if (stack.Count >= explosive.Length)
    {
        // 스택 맨 위의 개체가 제거 요소의 맨 앞과 같을 때
        if(stack.Peek() == explosive[0])
        {
            // 임시 저장 변수 선언 후 비워준다.
            string temp = string.Empty;
            // 스택에서 맨 위의 객체를 제거 후 반환해 temp에 저장한다
            for (int j = 0; j < explosive.Length; j++)
                temp += stack.Pop();

            // temp에 저장된 값이 explosive와 같지 않다면
            if (explosive != temp)
                // 임시 변수에 저장한 요소의 k번쨰 요소를 스택에 삽입한다.
                for (int k = temp.Length - 1; k >= 0; k--)
                    stack.Push(temp[k]);
        }
    }   
}

// 스택에 문장이 남아있다면 남은 문장을 대입
if (stack.Count > 0)
    while (stack.Count > 0)
        sb.Append(stack.Pop());
// 문장이 없으면 FRULA 대입
else
    sb.AppendLine("FRULA");

// 남은 문장 출력
Console.WriteLine(sb);

 

후기

이번에는 자료구조 분류에서 문제를 풀어보았다. Stack을 처음 만져보는 듯한 느낌이 났다. 잘 배워두었다가 개인 포트폴리오 개발에 써먹어 볼 생각이다. 인벤토리 정렬이 되었든, 이벤트 처리가 되었든, 되돌리기가 되었든 간에 최적화된 프로그램을 만들려면 필요하다.