9935번: 문자열 폭발

https://www.acmicpc.net/problem/9935

 

---

스택을 활용하면 되는 문제다.

폭발 문자열에 해당하는 문자열이 스택의 탑에 오는 경우에 pop해버리면 된다.

 

 

첫 풀이

import sys
input = sys.stdin.readline

word = input().rstrip()
bomb = input().rstrip()

len_word = len(word)

while True:
    word = word.replace(bomb, '')

    if len_word == len(word):
        break
    else:
        len_word = len(word)


if word == '':
    print('FRULA')
else:
    print(word)

 

처음에는 replace를 사용해서 풀었는데 바로 시간초과가 났다.

 

 

두번째 풀이

import sys
input = sys.stdin.readline

word = input().rstrip()
bomb = input().rstrip()
answer = ''


while True:
    arr = word.split(bomb)

    # 더 이상 폭발 문자열이 없는 경우
    if len(arr) == 1:
        answer = arr[0]
        break
    # 빈 문자열이 되는 경우
    word = ''.join(arr)
    if word == '':
        answer = 'FRULA'
        break

print(answer)

 

두번재 풀이는 폭발 문자열로 split을 해서 풀었는데 또 시간초과가 났다.

 

결국 스택을 사용해야겠다.

라는 생각으로 좀 풀다가 계속 시간초과가 나서 풀이를 실눈 뜨고 1초 동안 보는 방식으로 참고했다.

 

풀이

import sys
input = sys.stdin.readline

word = input().rstrip()
bomb = input().rstrip()
n = len(bomb)

stack = []


for w in word:
    stack.append(w)

    # 만약 스택의 top이 폭발 문자열의 마지막 문자와 같은 경우
    if stack[-1] == bomb[-1]:
        # 그리고 스택의 길이가 폭발 문자열의 길이 이상인 경우
        if len(stack) >= n:
            # 스택의 뒷부분이 폭발 문자열과 같다면 폭발 문자열을 pop한다.
            if ''.join(stack[-n:]) == bomb:
                for _ in range(n):
                    stack.pop()



if stack:
    print(''.join(stack))
else:
    print('FRULA')

 

내가 스택을 사용해서 풀었을 때, 계속 시간초과가 나길래 for문 안에 for문이 또 있으면 안되나 보다.

라고 생각하고 그렇게 풀려는데 도저히 모르겠어서 풀이를 본거였는데

결국 내가 생각한 아이디어와 거의 동일한 풀이가 있었다.

 

다 푼건데 못 푼 문제라서 화가 난다. ㅎㅎ

다음에 또 풀어볼 문제.