티스토리 뷰
문제
https://www.acmicpc.net/problem/9935
9935번: 문자열 폭발
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모
www.acmicpc.net
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
내 답안
myString = input().strip()
target = input().strip()
stack = []
target_ = len(target)
for i in range(len(myString)) :
stack.append(myString[i])
if ''.join(stack[-target_:]) == target :
for j in range(target_):
stack.pop()
if stack :
print("".join(stack[:]))
else :
print("FRULA")
해설
처음엔 while 문과 replace 내장함수로 특정 문자열이 있으면 전부 빈 문자열로 교체하는 방식으로 구현했는데 아니나 다를까 시간초과가 났다. 내장함수를 쓰지 않고 어떻게 해결해야 할 지 감이 잡히지 않아 알고리즘 분류를 보니 스택이 있길래 여기서 힌트를 얻었다.
입력받은 문자열에서 한 문자씩 stack에 넣은 후, stack에 들어간 문자들 중 폭발 문자열을 이루는 집합이 있다면 폭발 문자열의 길이만큼 pop한다.
피드백
- stack 자료구조는 파이썬에서 일반 list로 구현 가능함. append와 pop 함수는 기본적으로 내장되어 있음.
- 자료구조 문제도 많이 풀어봐야겠다. 그래프 아니면 해결 방안이 도통 생각나지 않는다..
'PS > 백준 boj' 카테고리의 다른 글
백준 17298 | 오큰수 | python 풀이 (1) | 2024.02.23 |
---|---|
백준 6198 | 옥상 정원 꾸미기 | python 풀이 (1) | 2024.02.23 |
백준 13023 | ABCDE | python 풀이 (0) | 2023.08.04 |
백준 16234 | 인구이동 | python 풀이 (0) | 2023.08.03 |
백준 7576 | 토마토 | python 풀이 (0) | 2023.08.02 |