| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 128 MB | 74022 | 19386 | 13731 | 26.047% |
문제
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
답안
import sys
whole_string = sys.stdin.readline().rstrip()
target_string = sys.stdin.readline().rstrip()
buffer = ""
stack = []
i = -1
while i < len(whole_string)-1:
i += 1
if i < len(whole_string) and whole_string[i] == target_string[0]:
j = 0
while whole_string[i+j] == target_string[j]:
buffer += whole_string[i+j]
j += 1
if j >= len(target_string):
buffer = ""
break
if i+j >= len(whole_string):
break
i += (j-1)
if buffer:
stack.append(buffer)
buffer = ""
else:
if len(stack) == 0:
stack.append(whole_string[i])
continue
if stack[-1] + whole_string[i] == target_string:
stack.pop()
continue
stack[-1] += whole_string[i]
print('FRULA' if len(stack) == 0 else ''.join(stack))풀이
이 문제에 주어진 문자열의 길이는 100만이다. 알고리즘으로는 힘들 수 있다는 말이다.
자료구조를 잘 활용한다면 최대 100만 길이의 문자열을 한 번만 훑어보더라도 문제를 풀 수 있을 것이라는 생각이 들었고, 그렇게 짜보기로 했다.
내가 문제 풀이를 위해 생각했던 자료구조는 stack이었다. stack에 문자열 덩어리들을 쌓아놓은 뒤, 만약 문자열 덩어리가 폭발 문자열일 경우 그 element를 pop해주면 되기 때문이다.
이렇게 하면 이전의 문자열 덩어리들이 다음에 올 문자열과 합쳐져 폭발 문자열이 되는 경우도 처리해줄 수 있었다.
whole_string = sys.stdin.readline().rstrip()
target_string = sys.stdin.readline().rstrip()
buffer = ""
stack = []
i = -1
while i < len(whole_string)-1:
i += 1입력을 받고, 임시로 문자열을 저장하는 buffer와 문제 풀이를 위해 필요한 stack을 초기화해줬다.
우리가 살펴볼 문자열의 길이만큼 반복하도록 했다.
if i < len(whole_string) and whole_string[i] == target_string[0]:
while whole_string[i+j] == target_string[j]:
...
else:
if len(stack) == 0:
stack.append(whole_string[i])
continue
if stack[-1] + whole_string[i] == target_string:
stack.pop()
continue
stack[-1] += whole_string[i]큰 구조를 먼저 살펴보면, 우선 지금 살펴보는 문자열이 폭발 문자열이 될 수도 있는 경우와 그렇지 않은 경우를 분리하여 생각하고 있다.
위쪽이 지금 살펴보는 문자열이 폭발 문자열이 될 수도 있는 경우이고, 이때 폭발 문자열의 길이만큼 반복해주면서(j) 폭발 문자열과 일치하는 만큼 버퍼에 저장한 뒤 스택에 넣어주고 있다.
아래쪽이 그 자체로 폭발 문자열이 되지 못하는 경우이다.
- 스택이 비어 있는 경우에는 스택에 append를 해주고,
- 스택의 top에 위치한 문자열과 현재 문자를 합했을 경우에 폭발 문자열이 되는 경우에는 스택을 pop해주고,
- 그 외의 모든 경우에는 (stack이 비어 있지 않으면서, stack 안에 있는 모든 문자열들이 폭발 문자열이 될 가능성이 없는 경우) stack의 top에 위치한 문자열에 지금의 문자를 더해준다.
이렇게 하면 스택에는 폭발 문자열이 될 수 있는 후보, 폭발 문자열이 전혀 될 수 없는 문자열들이 차례로 저장되게 된다.
모든 문자열을 살펴본 후에도 폭발 문자열이 될 수 있는 후보들이 실제로 폭발하지 않았다면, 그대로 출력해주면 된다.
print('FRULA' if len(stack) == 0 else ''.join(stack))이렇게 stack에 저장된 문자열들을 join하여 출력하면 된다.
이때
- 인덱싱이 잘 되고 있는지
- 빠진 범위는 없는지 (맨 처음, 맨 끝, 중간에 점프하는 구간)
- 범위를 넘어가도록 인덱싱하지 않고 있는지
- 버퍼를 잘 비워주고 있는지
- stack이 비어있는 경우의 예외 처리가 되었는지
- 폭발 문자열을 깔끔하게 지우도록 처리하고 있는지
등을 점검하는 것이 좋을 것이다.
