파이썬 문자열 연산에 대한 고찰 2

 

파이썬은 매우 편리한 언어이다. 그만큼 자칫하면 실수하기 쉬운 몇몇 기능들이 있다. 그중 하나를 소개하려고 한다.

 

이번에 소개할 착각하기 쉬운 연산은 in 연산과 == 연산이다.

 

==연산은 좌우가 같은지 확인하는 연산이고 문자열의 경우 두 문자열이 같은지 확인하는 연산이다. 이것은 두 문자열의 글자 하나하나 비교하는 것이므로 O(1)이 아닌 O(N)이다. 정수의 경우 O(1)이지만 문자열의 경우 'ss...sf' 와 'ss...sss' 를 비교하면 맨 마지막 글자까지 탐색하면서 O(N) 만큼의 시간이 걸리게 된다.

 

in 연산은 a in b 이런 식으로 a가 b 안에 속하는 지 확인할 때 사용하는 연산이다.

문자열의 경우 우리가 ctrl+F로 찾는 것처럼 a라는 문자열을 b에서 찾는 것이다. 이 경우 O(b*a) 만큼의 시간이 걸린다. a라는 문자열을 대조시키면서 진행하기 때문이다. in 연산 자체가 사실 set이나 dict같은 상황이 아니라면 O(N)의 시간이 걸리는데 같은지 확인하는데 이것은 즉 ==연산이다. 추가적으로 a의 길이만큼 시간이 걸리므로 O(b*a) 라는 시간복잡도를 갖는 것이다.

 

in 과 비슷한 find, count 모두 O(b*a) (a는 찾을 문자열 b는 검색에 사용할 문자열) 이라는 시간복잡도를 갖는다.