[백준] 9935번 문자열 폭발
문제 링크
https://www.acmicpc.net/problem/9935
문제 설명
- 전체 문자열과 폭탄 문자열이 주어짐
- 폭탄 문자열이 존재하면 없애고 이어 붙임
- 반복 후 남은 문자열 출력
시도1
접근
- 길이가 100만인건 봤는데 그냥 find 함수 써서 구현했다
- 시간 초과가 났다
- O(N^2)이라 그런 것 같다
- ex) 전체가 1111122222, 폭탄이 12일 때
코드
import sys
read = sys.stdin.readline
string = read().rstrip()
bomb = read().rstrip()
while True:
result = []
finished = True
while True:
i = string.find(bomb)
if i < 0:
result.append(string)
break
else:
result.append(string[:i])
string = string[i+len(bomb):]
finished = False
string = ''.join(result)
if finished:
break
if string:
print(string)
else:
print('FRULA')
시도2
접근
- 알고리즘 유형을 봤는데 스택이 있어서 생각해보니 떠올랐다
- 스택을 사용하면 삭제한 후 처음부터 다시 보지 않아도 된다
- 폭탄이 있으면 개수만큼 pop
- 없으면 append
- O(N)
코드
import sys
read = sys.stdin.readline
string = read().rstrip()
bomb = read().rstrip()
# 초기화
stack = []
i = 0
while True:
# 길이가 넘고 같을 때 pop
if len(stack) >= len(bomb):
if ''.join(stack[len(stack) - len(bomb):len(stack)]) == bomb:
for _ in range(len(bomb)):
stack.pop()
if i >= len(string):
break
# 다음거 append
stack.append(string[i])
i += 1
# 출력
if stack:
print(''.join(stack))
else:
print('FRULA')
Author And Source
이 문제에 관하여([백준] 9935번 문자열 폭발), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-9935번-문자열-폭발
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
접근
- 길이가 100만인건 봤는데 그냥 find 함수 써서 구현했다
- 시간 초과가 났다
- O(N^2)이라 그런 것 같다
- ex) 전체가 1111122222, 폭탄이 12일 때
코드
import sys
read = sys.stdin.readline
string = read().rstrip()
bomb = read().rstrip()
while True:
result = []
finished = True
while True:
i = string.find(bomb)
if i < 0:
result.append(string)
break
else:
result.append(string[:i])
string = string[i+len(bomb):]
finished = False
string = ''.join(result)
if finished:
break
if string:
print(string)
else:
print('FRULA')
시도2
접근
- 알고리즘 유형을 봤는데 스택이 있어서 생각해보니 떠올랐다
- 스택을 사용하면 삭제한 후 처음부터 다시 보지 않아도 된다
- 폭탄이 있으면 개수만큼 pop
- 없으면 append
- O(N)
코드
import sys
read = sys.stdin.readline
string = read().rstrip()
bomb = read().rstrip()
# 초기화
stack = []
i = 0
while True:
# 길이가 넘고 같을 때 pop
if len(stack) >= len(bomb):
if ''.join(stack[len(stack) - len(bomb):len(stack)]) == bomb:
for _ in range(len(bomb)):
stack.pop()
if i >= len(string):
break
# 다음거 append
stack.append(string[i])
i += 1
# 출력
if stack:
print(''.join(stack))
else:
print('FRULA')
Author And Source
이 문제에 관하여([백준] 9935번 문자열 폭발), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-9935번-문자열-폭발
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
read = sys.stdin.readline
string = read().rstrip()
bomb = read().rstrip()
# 초기화
stack = []
i = 0
while True:
# 길이가 넘고 같을 때 pop
if len(stack) >= len(bomb):
if ''.join(stack[len(stack) - len(bomb):len(stack)]) == bomb:
for _ in range(len(bomb)):
stack.pop()
if i >= len(string):
break
# 다음거 append
stack.append(string[i])
i += 1
# 출력
if stack:
print(''.join(stack))
else:
print('FRULA')
Author And Source
이 문제에 관하여([백준] 9935번 문자열 폭발), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-9935번-문자열-폭발저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)