처음 풀었을 때 시간초과 나서, 다른 분 풀이 보고 스택을 써야한다는 아이디어를 얻어 다시 코딩해서 pass했다.
- 사용 자료구조 : 문자열 + 스택
- 코드 설명 아래 주석에 달아놓았다.
- 핵심 아이디어는
- 폭발 문자열의 마지막 글자가 현재 탐색하는 문자와 같고,
- 폭발 문자열과 스택에 폭발 문자열의 길이만큼의 문자열이 같다면,
- 스택에서 폭발 문자열의 길이만큼 pop() 해준다.
- 마지막 문자까지 모든 탐색이 끝났을 때,
- 스택에 남아있는 문자가 있다면 스택을 문자열 형식으로 출력하고,
- 문자가 남아있지 않다면 "FRULA"를 출력한다.
파이썬 코드는 다음과 같다.
from sys import stdin
input = stdin.readline
def solve():
blen = len(bomb_temp) # 폭발 문자열의 길이
last_bomb = bomb_temp[-1] # 폭발 문자열의 마지막 글자
stack = []
for char in temp:
stack.append(char)
if char == last_bomb and bomb_temp == stack[-blen:]:
for _ in range(blen): # 길이만큼 stack의 문자 삭제
stack.pop()
result = ''.join(stack)
if result:
return result
else:
return "FRULA" # 남은 문자 없으면
# main
temp = input().strip() # 전체 문자열
bomb_temp = list(input().strip()) # 폭발 문자열
print(solve())
- 시간 : 208ms / 메모리 : 185620kb
- 고찰 : 문자열 문제를 근래에 많이 안 풀어서 이번 주는 문자열 위주로 좀 파야겠다. 문자열은 뭔가 유형이 돌고 도는 문제들이 많으니 좀더 익숙해질 필요가 있겠다.
'Problem Solving > boj' 카테고리의 다른 글
[BOJ] 1747. 소수&팰린드롬(Python) (0) | 2021.04.29 |
---|---|
[BOJ] 4358. 생태학(Python) (0) | 2021.04.29 |
[BOJ] 1316. 그룹 단어 체커(Python) (0) | 2021.04.27 |
[BOJ] 13335. 트럭(Python) / Simulation (0) | 2021.04.21 |
[BOJ] 3980. 선발 명단(Python) / DFS, Backtracking (0) | 2021.04.15 |