https://www.acmicpc.net/problem/9935
문제 파악
예제로 흐름을 파악해보자.
예제 입력 1에서 문자열은 "mirkovC4nizCC44", 폭발 문자열은 "C4", 출력은 "mirkovniz" 이다.
이건 총 두 번의 폭발이 일어난 결과다.
1) mirkovC4nizCC44
문자열에서 폭발 문자열 C4를 찾는다. 동시에 터지고, 남은 조각을 이어붙인다.
2) 이어붙인 문자열에서도 C4가 있으면 또 폭발.
폭발 문자열이 없을 때까지 계속 반복한다.
내 접근
처음엔 while로 반복을 돌렸다. 조건은 심플하게
문자열 string 안에 폭발 문자열 bomb_word가 더 이상 없을 때까지.
처음 감으로는 아래처럼 체크하려고 했다:
if bomb_word in string:
print("폭발물이 문자열안에 존재합니다.")
else:
print("폭발물이 없습니다.")근데 여기서 한 번 막혔다. 중간에 폭발 문자열이 있는 경우를 놓치는 순간이 있었음.
원인은 입력 처리였다. 나는 sys.stdin.readline()으로 받았는데, 이건 끝의 개행 \n까지 읽어온다. 그래서 실제 비교는 "abcd\n" vs "bc\n" 같은 식으로 흘러가 버린다. 그러면 당연히 중간 매칭이 어긋난다.
정리: 개행 때문에 불필요한 불일치가 생긴다 → 입력 받을 때 strip() 또는 rstrip("\n")으로 정리해야 한다. 이 순간 왜 사람들이 strip()을 습관처럼 쓰는지 이해했다.
그리고 제거 자체는 문자열 메소드 replace(제거할 것, 대체할 것)로 간단히 가능하다. 다만 이 문제는 문자열이 길어서 replace 반복은 시간초과가 난다. 그래서 스택으로 가야 한다.
해답 및 풀이 (처음 시도: replace 기반)
import sys
input = sys.stdin.readline
string = input().strip()
bomb_word = input().strip()
while bomb_word in string:
string = string.replace(bomb_word, "")
print("FRULA" if len(string) == 0 else string)- 아이디어는 직관적이라 구현은 쉬운데, 문자열이 길면 매번 새 문자열을 만들기 때문에 시간 초과가 났다.
스택을 사용한 해답 및 풀이 (정답)
문자를 하나씩 스택에 넣다가, 스택 끝부분이 폭발 문자열과 같으면 그 구간만 지운다. 이러면 전체를 계속 갈아엎지 않아도 돼서 빠르다.
import sys
input = sys.stdin.readline
string = input().strip()
bomb_word = input().strip()
stack = []
n = len(bomb_word)
for ch in string:
stack.append(ch)
# 스택 끝부분이 bomb_word와 같으면 폭발
if ''.join(stack[-n:]) == bomb_word:
del stack[-n:]
result = ''.join(stack)
print(result if result else "FRULA")stack[-n:] == list(bomb_word): 스택의 끝 n글자가 폭발 문자열과 동일하면 폭발.del stack[-n:]: 끝에서 n개 삭제(그 자리만 깔끔하게 잘라냄).- 마지막에
''.join(stack)으로 결과 문자열을 만든다.
내가 헷갈렸던 포인트들 정리
\n은 문자다. 중간 매칭을 하고 싶으면 개행을 맞춰줘야 한다.
입력에서rstrip("\n")(또는strip())으로 끝 개행을 정리하고 비교하자.''.join(stack[-n:])는 “스택 끝에서 n개를 뽑아 문자열로 합친다” 라는 뜻.
여기선 성능상stack[-n:] == list(bomb_word)비교가 더 낫다(불필요한 join 제거).del은 리스트 요소/슬라이스 삭제.
del stack[-n:]는 “스택 끝의 n개를 없애라” 는 뜻.
