티스토리 뷰

문제

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 함수는 기본적으로 내장되어 있음.
  • 자료구조 문제도 많이 풀어봐야겠다. 그래프 아니면 해결 방안이 도통 생각나지 않는다..
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/05   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
글 보관함