문제 링크

문제 소개

해당 문제는 전체 문자열 중 특정 문자열이 들어갔을 경우 없애는 작업을 반복했을 때, 더이상 없어지지 않는 문자열이 무엇임을 알아내는 문제이다.

문제 분석

해당 문제를 풀기 위해 아래의 코드와 같이 러프하게 풀어봤다.

import sys


def solution():
    input = sys.stdin.readline
    target, explosion = list(input().rstrip('\n')), list(input().rstrip('\n'))

    while True:
        flag = True
        nextTarget = ''
        i = 0
        while i < len(target):
            if target[i] == explosion[0]:
                if target[i:i + len(explosion)] == explosion:
                    flag = False
                    i += len(explosion)
            else:
                nextTarget += target[i]
            i += 1
        target = nextTarget
        if flag:
            print(target)
            break


solution()

당연하게도 시간초과가 발생하였다. 어떤 부분이 시간초과가 발생하는지 아래와 같이 정리하였다.

문제점

1. 특정 문자열이 폭발했는지 못했는지는 코드를 한번 더 진행해야 알수있음

2. 포인터로 움직이면서 처리하기에는 너무 많음(전체 문자열 크기가 10^6)

그럼으로 위의 문제점을 하나씩 개선해볼 것이다.

우선, 위의 방법은 우선 특정 문자열을 지워보고 전체 문자열의 before,after를 비교하였다. 하지만, 굳이 전체를 여러번 확인할 필요가 있을까?

문제점의 핵심 해결책은 바로 stack을 사용하는 것이다. 문제를 풀어내기위해 아래와 같이 알고리즘을 정리하였다.

문제점의 해결 알고리즘

1. stack 리스트를 생성해서 거기에다 전체 문자열에서 문자 하나하나씩 가져옴

2. 이렇게 가져왔을 때, 특정 문자열일 경우 stack 리스트에서 지워버림

위의 알고리즘의 개선사항은 아래와 같다.

문제점 해결 알고리즘 개선사항

• 특정 문자열과 비교할 때, 슬라이싱 사용하되 첫번째 값을 먼저 비교해봄으로서 불필요한 슬라이싱 줄임
• 문자열 삭제시 del함수 사용

위와 같은 알고리즘을 구현해보면 아래와 같다.

전체 코드

import sys


def solution():
    input = sys.stdin.readline
    target, explosion, = list(input().rstrip('\n')), list(input().rstrip('\n'))
    stack = []
    for i in target:
        stack.append(i)
        if i == explosion[-1] and stack[-len(explosion):]==explosion:
            del stack[-len(explosion):]

    print(''.join(stack) if stack else "FRULA")


solution()