[Time Complexity 분석] BOJ 9935 문자열 폭발

https://www.acmicpc.net/problem/9935

 

 

주어질 문자열의 길이를 N, 폭발 문자열의 길이를 M이라고 하자.

가장 먼저 무식하게 하는 방법은 아래와 같다.

# 1. 무식한 방법

string = input()
s = input()
length = len(s)

while True:
    if s in string:
        index = string.index(s)
        string = string[:index] + string[index+length:]

    else:
        break

print(string if string else "FLURA")

 

python에서 문자열 슬라이싱의 시간 복잡도는 O(K) where K is length of the slice.

< if s in string: > 이라는 코드는, s가 한 문자가 아닌 문자열이므로, 시간복잡도는 O(NM) 이 될것이다.

최악의 경우, break 되지 않고 while 문이 끝까지 실행되는 것이다. 

이 경우는 O(N)에 해당이 된다.

 

최종적으로, O(N^2 * M)의 시간복잡도를 가진다.
일반적으로 M이 N보다 훨씬 작으므로, O(N^2)에 근사하는 값을 가질 것이다.

이 시간복잡도를 가지고 문제 제출을 할 시 "시간 초과"

 

 

아래는 시간 효율성을 증가시킨 코드이다.

# 2. 효율적인 방법

from collections import deque

string, s = list(input()), list(input())
length = len(string)

arr = deque()

def is_including(arr, s):
    if len(arr) < len(s):
        return False

    for i in range(len(s)):
        if arr[i] != s[i]:
            return False

    return True


for i in range(length-1, -1, -1):
    arr.appendleft(string.pop())

    if is_including(arr, s):
        for _ in range(len(s)):
            arr.popleft()


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

 

플로우는 다음과 같다.

1. 문자열에서 마지막 문자를 pop하고, 임시 문자열인 arr에 왼쪽에 삽입한다.
         -  (arr는 deque 자료형이라 appendleft() 를 O(1)에 처리할 수 있다.)
2. 임시 문자열 arr에 대해서, 첫 문자부터 폭발 문자열와 일치하는지 확인한다.
3. 폭발 문자열과 일치한다면, arr에서 반복적인 popleft() 를 통해 폭발 문자열을 pop() 한다.
4. 폭방 문자열과 일치하지 않는다면, skip 하고 1 번부터의 과정을 반복한다.

기본적으로 is_including() 함수는 O(M)의 시간복잡도를 가진다. 

아래 for 루프는 N번 반복하고, 내부 로직에 O(M)을 가지는 is_including() 이 실행되고, 폭발 문자열의 길이(M) 만큼 arr에서 pop을 한다.

deque() 자료형이므로 appendleft, popleft() 등의 함수는 O(1)의 시간복잡도를 가지고, 리스트에서 pop()은 O(1)을 가진다.

최종적으로, O(NM)의 시간복잡도를 가지게 된다.

 

M이 N에 비해 훨씬 작으므로, 최악의 경우에도 O(N) 이라는, 선형시간에 문제를 해결할 수 있다.