[BOJ][🟡4][백준#09935] 문자열 폭발

문제 출처

BAEKJOON Online Judge #9935

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다.

문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, …, 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

예제

예제 1

입력

mirkovC4nizCC44
C4

출력

mirkovniz

예제 2

입력

12ab112ab2ab
12ab

출력

FRULA

My Sol

import sys
input = sys.stdin.readline

def check(idx):
    global part, pl
    stack = stacks[idx]

    if len(stack) != pl: return 0

    for i in range(pl):
        if not part[i] == stack[i]: return 0
    return 1


txt = input().rstrip()
part = input().rstrip()
pl = len(part)
stacks = [[]]
ls = [0]

cur_stack_idx = 0
k = 0
for t in txt:
    if t == part[k]:
        stacks.append([t])
        cur_stack_idx += 1
        ls.append(1)

    else:
        stacks[cur_stack_idx].append(t)
        ls[cur_stack_idx] += 1

    # 현재 stack에 모인 문자가 pl과 같을 때
    if ls[cur_stack_idx] == pl:
        while check(cur_stack_idx):
            stacks.pop()
            ls.pop()
            cur_stack_idx -= 1


def is_empty(stacks):
    for stack in stacks:
        if stack: return 0
    return 1

if is_empty(stacks):
    print('FRULA')
    quit()

for stack in stacks:
    print(*stack, sep='', end='')

스택을 이용해 푸는 문제였다.

1. stack을 모아놓은 stacks 리스트 생성
2. 폭발 문자열의 첫 문자를 발견할 때마다 새 stack에 추가
3. stack의 길이가 part의 길이와 같아지면 같은지 체크하는 함수 실행
4. 만약 같다면 stack을 stacks에서 제거
5. 새로운 t가 이전 stack에 계속 추가되어 pl과 같아지면 다시 check
6. 이 과정을 반복
7. 남은 stacks를 공백 간격 없이 출력
8. 만약 stacks가 비어있다면 FRULA 출력

리스트 내부에 빈 리스트가 하나 있으면 False가 아닌 True인 것에 주의해야 했다.

결과

맞았습니다!!

처음에는 list를 이용해 폭발 문자열을 발견하면 폭발 문자열의 길이만큼 pop하여 제거하는 과정을 반복했는데, 시간 초과가 발생해서 알고리즘 분류를 참고하였다.

모범답안

def main():
 
    string = input()    # 전체 문자열
    bomb = input()      # 폭발 문자열
 
    lastChar = bomb[-1] # 폭발 문자열의 마지막 글자
    stack = []
    length = len(bomb)  # 폭발 문자열의 길이
 
    for char in string:
        stack.append(char)
        if char == lastChar and ''.join(stack[-length:]) == bomb:
            del stack[-length:]
 
    answer = ''.join(stack)
 
    if answer == '':
        print("FRULA")
    else:
        print(answer)

내 풀이에 비해 코드길이는 약 45%, 연산시간은 약 25% 정도인 풀이(출처)를 발견해 분석해보려 한다.

이 분의 접근은 다음과 같다.

1. 입력문자열을 앞에서부터 차례차례 한 글자씩 스택에 push 합니다.

2. 현재 글자가 폭발 문자열의 마지막 글자와 일치하면 스택의 top부터 폭발문자열의 길이까지 확인하여 폭발문자열이 만들어지는지 확인합니다.

3. 폭발문자열이 만들어진다면 만들어지는 폭발문자열을 스택에서 pop합니다.

4. 1~3을 반복합니다.

5. 문자열 순회를 마치고 스택이 비어있으면, FRULA를 출력, 비어있지 않다면 스택 속 문자열을 차례로 출력합니다.

뒤에서부터 확인하면 될 일이었다. 굉장히 똑똑한 풀이라고 생각한다. 나처럼 다중 stack을 사용하지 않고 하나의 stack으로만 해결한 것이니 말이다. 이렇게 되면 stacks가 비어있는지 확인하는 함수 역시 필요가 없다.

다만 answer에 답을 모아서 출력했는데, 나는 별도의 메모리 사용 없이 바로 출력하기 위해 is_empty 함수를 만들었다. 이 분은 if stack: 으로 FRULA를 출력하거나 출력 형식에 따라 바로 출력할 수 있었는데 해당 부분은 아쉽다. 그럼에도 전체적으로 너무나 훌륭한 접근과 풀이였다.