Python String concatenation
파이썬의 string은 int, tuple 등과 같이 immutable한 속성을 가지고 있다.
string은 +기호를 통해 직관적으로 concatenation 연산을 수행할 수 있는데, 자료구조에 대해 잘못 이해하면 비효율적인 코드를 짜게될 수 있다.
파이썬의 concatenation은 새로운 문자열을 만드는 것이므로, 해당 문자열의 길이만큼 시간이 걸리게 된다. (필요한 공간도 마찬가지)
예를 들어 s라는 문자열에 동일한 길이의 s1, s2 리스트의 값 중 더 큰 값을 넣는 문제가 있다고 하자.
s = ""
for i in range(len(s1)):
if s1[i] >= s2[i]:
s += s1[i]
else:
s += s2[i]s의 길이는 1씩 증가하므로 for문이 다 돌때까지 걸리는 시간은 1 + 2 + ... + N = N(N+1)/2 즉, O(N^2)이고, 공간복잡도 역시 O(N^2)가 된다.
해결
List를 적절하게 사용하여 해결해야 하고 필요하다면 join 연산을 이용할 수 있다.
