Python String concat 시간 복잡도

두 문자열을 합치는 것을 string concatenation이라고 한다.

 

파이썬에서는 이를 + 기호를 이용해 직관적이고 간단하게 할 수 있으며, 이렇게 문자열을 쉽게 다룰 수 있는 것이 파이썬의 강점 중 하나이다.

 

그러나 자료구조에 대한 면밀한 이해가 없으면 string concatenation을 오용하여 비효율적인 코드를 짜게 될 수 있다.

 

이러한 사실을 모르고 있었기에 비효율적인 코드를 작성 하고 있었다.

 

비효율적인 코드 보단 효율적인 코드를 위해서 조사를 하게 되었다.

 

우선

def solution(s1: str, s2: str) -> str:
    s = ""
    for i in range(len(s1)):
        if s1[i] >= s2[i]:
            s += s1[i]
        else:
            s += s2[i]
    return s

이러한 코드가 있다고 가정 해보자

 

이 풀이는 간단하고 이해하기 쉽지만 비효율적이다. 왜 그럴까?

 

파이썬에서 string concatenation은 새로운 문자열을 만드는 것이다.

 

예를 들어 s = s1 + s2를 실행할 때, 파이썬은 우선 s1을 새 공간에 복사하고 그 뒤의 공간에 이어서 s2를 복사한다.

 

그리고 이 새로운 문자열의 주소값을 s에 할당한다.

 

그러므로 이 연산에 걸리는 시간은 s1의 길이 + s2의 길이만큼이며, 필요한 공간도 마찬가지로 s1의 길이 + s2의 길이이다.

 

다시 위의 풀이를 보자. 매 for문마다 s += s1[i] 혹은 s += s2[i]가 실행되고 있다.

 

이는 곧 매 주기마다 문자열 s의 복사가 일어난다는 것을 의미한다. s의 길이는 1씩 증가하므로 for문이 다 돌때까지 걸리는

 

시간은 1 + 2 + … + N = N(N + 1) / 2 이고 시간복잡도는 O(N^2)이다.

 

마찬가지로 공간복잡도 역시 O(N^2)이다.

 

직관적으로 보았을 때 선형 시간 안에 풀리는 문제를 다항 시간에 풀고 있으므로 이 풀이는 비효율적이다.

 

해결책: List 사용하기

 

이 문제의 좀 더 효율적인 풀이는 다음과 같다.

def solution(s1: str, s2: str) -> str:
    s_as_list = []
    for i in range(len(s1)):
        if s1[i] >= s2[i]:
            s_as_list.append(s1[i])
        else:
            s_as_list.append(s2[i])
    return "".join(s_as_list)

 

이 풀이에서는 두 문자열을 순회하며 각 인덱스에서 더 큰 문자를 리스트에 append하고,

 

마지막에 join을 이용해 문자열을 만들어 리턴한다. 매 for문마다 일어나는 append는 상수 시간 연산이기 때문에 최종적인 시간복잡도는 O(n)이며,

 

리스트와 마지막에 리턴하는 문자열 외에 다른 자료구조를 사용하지 않기 때문에 공간복잡도도 O(n)이다.

 

Immutable한 객체인 문자열 대신 mutable한 객체인 리스트를 사용함으로서 문자열을 가변적으로 관리하여 효율성을 달성