백준 - 문자열 폭발 / Gold 4 / 9935번 / Python

문제 📋

백준 - 문자열 폭발

target이 없을 때까지 계속해서 모든 target을 찾아 제거하는 문제이다.

input_string의 최대 길이가 1,000,000 (이하 n)이고
target의 최대 길이가 36 (이하 k) 이기 때문에
시간 복잡도를 최적화하는 게 제일 중요한 문제이다.

이 문제를 풀면서 겪었던 모든 풀이에 대해 시간 복잡도를 분석해 보겠다.

시간초과 풀이1 📝

import sys


def solution(target, input_string):
    seperated_string = input_string.split(target)

    while len(seperated_string) > 1:
        new_string = "".join(seperated_string)
        seperated_string = new_string.split(target)

    new_string = "".join(seperated_string)
    
    if not new_string:
        new_string = "FRULA"
    return new_string


input_string = sys.stdin.readline().rstrip()
target = sys.stdin.readline().rstrip()

print(solution(target, input_string))

먼저 이 풀이의 아이디어는 split(target) 함수를 통해 target을 자동으로 제거하고
join을 통해 이어준 뒤 반복하는 것이다.

이 풀이의 시간 복잡도

• while 문 : target들을 제거하는 횟수 m
  • split() : O(n)
  • join() : O(n)

총 시간 복잡도는 O(mn)인데 생각보다 m이 worst case에서는 컸던 것 같다.

시간초과 풀이2 📝

import sys


def solution(target, input_string):
    stack = []

    for char in input_string:
        stack.append(char)

        if len(stack) < len(target):
            continue

        temp = ""
        for i in range(len(stack)-len(target), len(stack)):
            temp += stack[i]

        if temp == target:
            for _ in range(len(target)):
                stack.pop()
    if not stack:
        stack.append("FRULA")
    return "".join(stack)


input_string = sys.stdin.readline().rstrip()
target = sys.stdin.readline().rstrip()

print(solution(target, input_string))

이 풀이는 stack에 문자를 하나씩 넣으면서
뒤에서부터 target을 확인하여 pop 해주는 방식이다.

이 풀이의 시간 복잡도

• for 문 : O(n)
  • 두 번째 for 문 : O(k)
    • string concat : O(len(stirng))

stack에 있는 문자들을 target 길이만큼 슬라이싱 할 경우 메모리에 부담이 예상되어서 생각해낸 방식인데 string concat의 시간 복잡도를 예상치 못했다.

Python에서 string을 이어붙일 때에는 각각의 길이만큼 복사하여 새로운 string을 만들기 때문에 길이의 합만큼의 시간 복잡도가 더해진다.

그런데 해당 작업을 2중 for 문 내에서 하고 있어서 제일 성능이 좋지 못했다.

모두 통과한 풀이 📝

import sys


def solution(target, input_string):
    stack = []

    for char in input_string:
        stack.append(char)

        if len(stack) < len(target):
            continue

        temp = stack[-len(target):]

        if "".join(temp) == target:
            for _ in range(len(target)):
                stack.pop()

    if not stack:
        stack.append("FRULA")

    return "".join(stack)


input_string = sys.stdin.readline().rstrip()
target = sys.stdin.readline().rstrip()
print(solution(target, input_string))

2번째 풀이에서 stack의 문자열을 target 길이만큼 슬라이싱 하도록 변경했다.
시간 복잡도는 O(kn)이기 때문에 통과했으며
걱정했던 공간 복잡도도 계산을 해보니 다음과 같았다.

• 메모리 제한 : 128MB
• 메모리 최대 사용량 : 36MB
  • target 최대길이 : 36바이트
  • 최대 1,000,000번 슬라이싱(복사)