[Python] 백준 9935번 - 문자열 폭발 (골드 4)

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 자료구조
 - 스택
 - 문자열

 

 

문제

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

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

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

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

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

입력

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

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

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

출력

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

 

---

 

문제 개요

백준 9935번 문제는 문자열 처리와 관련된 중요한 알고리즘 문제입니다. 이 문제에서는 주어진 문자열에서 특정 '폭발 문자열'을 모두 제거하는 과정을 구현해야 합니다. 문제의 핵심은 폭발 문자열이 사라지면 그 결과로 새로운 폭발 문자열이 생성될 수 있다는 점입니다.

문제 해결 전략

문제 해결의 핵심은 스택을 사용하는 것입니다. 스택을 활용하여 폭발 문자열을 효율적으로 처리할 수 있습니다. 이번 포스트에서는 파이썬을 사용한 해결 방법을 소개합니다.

 

 

import sys
input = sys.stdin.readline

# 입력 받은 문자열
s = input().rstrip()
# 폭발 문자열
bomb = input().rstrip()
length = len(bomb)

# 스택에 폭발 문자열이 있는지 확인하는 함수
def check():
    # 스택의 길이가 폭발 문자열의 길이보다 짧으면 반환
    if len(stack) < length:
        return
    # 스택의 끝 부분이 폭발 문자열과 일치하는지 확인
    tail = stack[len(stack)-length:]
    if ''.join(tail) == bomb:
        for i in range(length):
            stack.pop()

# 메인 로직
stack = []
for i in s:
    stack.append(i)
    check()
    
# 결과 출력
if len(stack) == 0:
    print("FRULA")
else:
    print(''.join(stack))

 

코드 설명

1. 입력 처리: sys.stdin.readline을 사용하여 입력을 빠르게 받습니다. .rstrip()은 줄 끝의 개행 문자를 제거합니다.
2. 변수 초기화: 입력 받은 문자열 s와 폭발 문자열 bomb, 그리고 폭발 문자열의 길이 length를 정의합니다.
3. check 함수: 스택의 마지막 부분이 폭발 문자열과 일치하는지 확인하고, 일치한다면 해당 부분을 스택에서 제거합니다.
4. 메인 로직: 문자열 s를 순회하면서 각 문자를 스택에 추가합니다. 이후 check 함수를 호출하여 폭발 문자열이 형성되었는지 확인합니다.
5. 결과 출력: 스택이 비어있다면("FRULA"), 그렇지 않다면 스택에 남은 문자열을 출력합니다.

결론

백준 9935번 문제는 스택을 활용하여 문자열을 효율적으로 처리하는 방법을 배울 수 있는 좋은 예제입니다. 이 문제를 통해 문자열 처리와 스택의 활용에 대해 더 깊이 이해할 수 있습니다.