[백준_스택2] 9935번 - 문자열 폭발

문제

9935번: 문자열 폭발

 

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

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

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

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

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

 

 

입력

 

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

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

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

출력

 

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

 

 

 

예제 입력

mirkovC4nizCC44
C4

 

 

예제 출력

mirkovniz

 

 

 

 

풀이

 

스택을 활용하여 문자열을 처리하는 방법은 다음과 같습니다.

1. 스택 생성: 먼저 빈 스택을 생성합니다. 스택은 후입선출(LIFO) 구조로, 문자열을 처리하는데 사용됩니다.

2. 문자열 순회: 주어진 문자열을 한 글자씩 순회하면서 스택에 문자를 하나씩 추가합니다.

3. 폭발 문자열 검사: 스택의 마지막 글자와 폭발 문자열의 마지막 글자를 비교합니다. 

만약 일치하면, 스택의 끝에서부터 폭발 문자열의 길이만큼의 부분 문자열을 확인하여, 폭발 문자열과 동일한지 검사합니다.

4. 폭발 문자열 제거: 만약 폭발 문자열과 스택의 부분 문자열이 일치하면, 스택에서 해당 부분을 제거합니다.

5. 문자열 처리 반복: 주어진 문자열의 모든 글자를 처리할 때까지 위의 단계를 반복합니다.

6. 결과 생성: 모든 문자열 처리가 끝나면, 스택에 남아있는 문자들을 합쳐서 최종 결과 문자열을 생성합니다.

아래는 이러한 스택을 활용한 문자열 처리 방법을 구체적인 예제와 함께 설명합니다:

 

 

예제로 설명

 

제가 이전에 작성한 설명에서 오타가 있었습니다. 죄송합니다. 아래는 올바른 과정을 설명한 것입니다.

1. 빈 스택을 생성합니다.

2. 문자열 "mirkovC4nizCC44"를 한 글자씩 순회하면서 스택에 문자를 추가합니다.
   - 스택: ['m', 'i', 'r', 'k', 'o', 'v', 'C', '4', 'n', 'i', 'z', 'C', 'C', '4', '4']

3. 스택의 마지막 글자 "4"와 폭발 문자열 "C4"의 마지막 글자 "4"를 비교하면 일치합니다.

4. 스택의 끝에서부터 폭발 문자열의 길이만큼 부분 문자열 "44"와 폭발 문자열 "C4"를 비교하여 일치하지 않으므로 다음 문자열로 넘어갑니다.

 

5. 스택 뒤에서 두 번째 글자 "4"와 폭발 문자열 "C4"의 마지막 글자 "4"를 비교하면 일치합니다.

 

6. 스택의 끝에서부터 폭발 문자열의 길이만큼 부분 문자열 "C4"와 폭발 문자열 "C4"를 비교하여 일치함으로 스택에서 "C4"을 제거합니다.

- 스택: ['m', 'i', 'r', 'k', 'o', 'v', 'C', '4', 'n', 'i', 'z', 'C', '4']

---

7. 문자열 처리를 계속하면 다음과 같은 스택이 생성됩니다.
   - 스택: ['m', 'i', 'r', 'k', 'o', 'v', 'n', 'i', 'z']

8. 마지막으로 스택에 남아있는 문자들을 합쳐서 최종 결과 문자열을 생성합니다.
   - 결과: "mirkovniz"

 

 

소스 코드

 

 

def explode_string(text, bomb):
    stack = []  # 스택을 사용하여 문자열을 처리할 리스트 생성

    # 문자열을 한 글자씩 읽으면서 스택에 문자를 추가
    for char in text:
        stack.append(char)

        # 스택의 마지막 글자가 폭발 문자열의 마지막 글자와 일치하고,
        # 스택의 끝에서부터 폭발 문자열 길이만큼의 부분 문자열이 폭발 문자열과 같다면 폭발 문자열 제거
        if char == bomb[-1] and ''.join(stack[-len(bomb):]) == bomb:
            del stack[-len(bomb):]

    result = ''.join(stack)  # 스택에 남은 문자열을 합침

    if result == '':
        return "FRULA"
    else:
        return result

# 입력 받기
text = input()
bomb = input()

# 결과 출력
result = explode_string(text, bomb)
print(result)