thenullpage.com
1. 문자열은 글자를 순서대로 담아둔 자료구조입니다
문자열(string)은 글자 하나하나를 순서대로 늘어놓은 자료구조입니다. 각 글자에는 0번부터 번호가 붙고 이 번호를 인덱스라고 부릅니다.
s = "hello"
print(s[0])
print(s[-1])
print(len(s))
h
o
5
글자들이 저장 공간에 나란히 붙어 있어서 시작 지점에 번호만 더하면 원하는 자리가 바로 계산됩니다. 그래서 s[0]으로 글자를 꺼내는 일은 문자열이 다섯 글자든 백만 글자든 걸리는 시간이 같습니다. 음수 인덱스는 뒤에서 세는 표기라 s[-1]은 마지막 글자입니다.
2. 문자열은 한 번 만들면 내용을 바꿀 수 없습니다
리스트는 nums[0] = 9처럼 특정 칸의 값을 그 자리에서 갈아끼울 수 있습니다. 문자열에 같은 짓을 하면 오류가 납니다.
s = "hello"
s[0] = "H"
TypeError: 'str' object does not support item assignment
문자열은 대부분의 언어에서 불변(immutable), 한 번 만들어지면 내용을 수정할 수 없는 값으로 정해져 있습니다. 파이썬 str도 자바 String도 그렇습니다. 첫 글자를 대문자로 바꾸려면 원하는 모양의 새 문자열을 만들어야 합니다.
s = "hello"
s = "H" + s[1:]
print(s)
Hello
첫 글자만 바뀐 것 같지만 실제로는 "H"와 "ello"를 이어붙인 새 문자열이 통째로 만들어지고 s라는 이름이 그 값을 가리키게 된 것입니다. 이 차이가 곧바로 성능 문제로 이어집니다.
3. 반복문 안에서 문자열을 더하면 왜 느려질까
문자열을 조금씩 만들어 나갈 때 가장 자연스럽게 손이 가는 코드가 result += ch 형태입니다. 문자열은 수정이 안 되니 더할 때마다 지금까지 쌓인 글자를 전부 새 공간에 복사한 뒤 끝에 한 글자를 붙입니다. 이미 만 글자가 쌓여 있다면 한 글자를 더하려고 만 글자를 복사하는 셈입니다.
대안은 조각을 리스트에 모아뒀다가 마지막에 join으로 한 번만 합치는 방식입니다. 두 방식을 나란히 재보겠습니다.
import time
for n in [50000, 100000, 200000]:
start = time.time()
s = ""
for i in range(n):
s += "a"
t1 = time.time() - start
start = time.time()
parts = []
for i in range(n):
parts.append("a")
s = "".join(parts)
t2 = time.time() - start
print(n, "더하기", round(t1, 4), "join", round(t2, 4))
50000 더하기 0.0499 join 0.004
100000 더하기 0.1574 join 0.0092
200000 더하기 0.591 join 0.0177
글자 수가 두 배 늘 때마다 더하기 방식은 시간이 세 배 넘게 뜁니다. 두 배면 두 배 정도여야 선형인데 그보다 가파르니 전체가 O(n^2)에 가깝다는 뜻입니다. 반면 join 쪽은 두 배씩만 늘어납니다. 조각들의 전체 길이를 먼저 더해 필요한 공간을 한 번에 확보한 뒤 옮겨 담으니 복사가 사실상 한 번뿐이고 전체가 O(n)입니다.
join 앞의 빈 문자열은 조각 사이에 끼울 구분자라 ",".join(parts)로 쓰면 조각마다 쉼표가 들어갑니다. 자바에서 반복문 안 문자열 더하기 대신 StringBuilder를 쓰라는 조언도 원리가 같습니다.
4. 슬라이싱은 생각보다 비싼 연산입니다
s[1:5]처럼 범위를 잘라내는 문법을 슬라이싱이라고 합니다. 슬라이싱도 잘라낸 부분을 담은 새 문자열을 만들어내므로, 잘라낸 길이만큼 복사가 일어납니다.
import time
big = "a" * 1000000
start = time.time()
for _ in range(1000):
x = big[:500000]
print("50만 글자씩", round(time.time() - start, 4))
start = time.time()
for _ in range(1000):
x = big[:10]
print("10글자씩", round(time.time() - start, 6))
50만 글자씩 0.2716
10글자씩 0.00019
같은 천 번인데 자르는 길이에 따라 천 배 넘게 차이가 납니다. 긴 문자열을 반복문 안에서 통째로 잘라 비교하는 코드는 반복문이 하나뿐이라 O(n)처럼 보여도 실제로는 O(n^2)입니다.
5. 한글은 글자 수와 바이트 수가 다릅니다
word = "한글을배워요"
print(len(word))
print(len(word.encode("utf-8")))
6
18
len은 글자 수를 세니 6이 나오지만, 파일에 저장하거나 네트워크로 보낼 때 차지하는 크기는 18바이트입니다. UTF-8 방식에서 한글 한 글자가 3바이트를 쓰기 때문입니다. 글자 단위 문제라면 len을 그대로 쓰면 되고, 용량 제한을 볼 때는 바이트 기준인지 글자 기준인지 확인해야 합니다.
6. 같은 글자로 이루어졌는지 판정하는 두 가지 방법
listen과 silent처럼 글자 구성은 같고 순서만 다른 두 단어를 아나그램이라고 부릅니다. 먼저 떠오르는 판정 방법은 두 단어를 각각 정렬해 비교하는 것입니다.
a = "listen"
b = "silent"
print(sorted(a))
print(sorted(a) == sorted(b))
['e', 'i', 'l', 'n', 's', 't']
True
sorted는 문자열을 글자 하나씩 담은 리스트로 만들어 정렬해줍니다. 정렬을 거치니 글자 수가 n일 때 O(n log n)이 듭니다. 각 글자가 몇 번 나왔는지 세어 비교하면 더 빠릅니다.
from collections import Counter
print(Counter("banana"))
print(Counter(a) == Counter(b))
Counter({'a': 3, 'n': 2, 'b': 1})
True
Counter는 글자별 등장 횟수를 세어주는 도구입니다. 문자열을 한 번만 훑으면 되니 O(n)이라 정렬보다 유리합니다.
7. 앞뒤에서 좁혀오는 투포인터
기러기처럼 거꾸로 읽어도 똑같은 문자열을 팰린드롬이라고 합니다. s == s[::-1]로 한 줄에 확인할 수도 있지만 뒤집은 문자열을 새로 만드느라 길이만큼 메모리를 더 씁니다. 추가 메모리 없이 확인하려면 양 끝에서 안쪽으로 좁혀오면 됩니다.
def is_palindrome(s):
left = 0
right = len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
print(is_palindrome("level"))
print(is_palindrome("python"))
True
False
양 끝 번호를 잡아 두 글자를 비교하고, 같으면 번호를 한 칸씩 안으로 옮깁니다. 두 번호가 만나면 끝까지 확인한 것이니 팰린드롬입니다. 위치 표시 두 개를 동시에 움직이는 이 기법을 투포인터라고 부릅니다.
8. 문자열을 다룰 때 기억해둘 것
문자열에서 생기는 성능 문제는 대부분 한 가지 사실에서 갈라져 나옵니다. 문자열은 고칠 수 없고, 모양이 달라진 문자열이 필요하면 매번 새로 만들어야 한다는 것입니다.
그래서 챙길 것은 세 가지입니다. 반복해서 이어붙일 때는 리스트에 모아 join으로 마무리하기, 반복문 안에서 긴 구간을 잘라내는 코드는 인덱스 비교로 바꿀 수 있는지 살펴보기, 글자를 세야 하는 문제는 정렬보다 빈도 세기를 먼저 떠올리기입니다.