<문자열 조작>
문자열 조작은 코딩 테스트에서 매우 빈번하개 출제되고 실무에서도 다양한 분야에 쓰이는 주제라고 한다.
- 정보 처리 분야웹 페이지를 탐색할 때 문자열 처리 애플리케이션을 이용하게 되며 문자열 처리는 정보 처리에 핵심적인 역할을 한다.
- 통신 시스템 분야
데이터 전송은 문자열 처리 알고리즘이 탄생한 배경 이기도 하며, 데이터 전송에서 문자열 처리는 매우 중요하다.
- 프로그래밍 시스템 분야
프로그램은 그 자체가 문자열이며, 컴파일러나 인터프리터는 문자열을 기계어로 번역하기 때문에 매우 정교한 문자열 처리 알고르짐 등이 사용된다.
이번 장에서는 파이썬 문자열 자료형에 있는 기능들과 문자열 조작과 처리에 사용되는 기법을 알아본다.
유효한 팰린드롬
leetcode의 125 문제인 Valid Palindrome 문제를 통해 파이썬의 문자열 조작에 대해서 알아보자.
문제 : palindrome은 앞 뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장을 말한다. 대소문자를 구분하지 않는다.
- 나의 풀이와 해답 풀이 3가지를 통해 문자열 조작에 대한 속도를 비교해 보겠다.
- 나의 풀이
def isPalindrome_mine(s:str)->bool:
strs=[]
# 먼저 문자를 변환한다 (공백을 제하고 소문자로 변경한다)
for char in s:
# 만약 char가 공백이면 strs에 추가한다.
# isalnum은 영문자,숫자 여부를 판별하는 함수이다.
if char.isalnum():
#str에 추가하는데, 소문자로 변환하여 추가한다.
strs.append(char.lower())
# 문자를 비교한다
# 반복문을 사용한다
# 첫 문자 != 끝 문자 -> false를 출력한다
# 반복문이 끝나면 true를 출력한다
length=len(strs)
for i in range(int(length/2)):
start=i
end=length-i-1
if(strs[start]!=strs[end]):
return False
return True
#---LeetCode 속도 측정 --#
# Runtime: 52 ms, faster than 47.40% of Python3 online submissions for Valid Palindrome.
# Memory Usage: 19.6 MB, less than 12.74% of Python3 online submissions for Valid Palindrome
- 위에서 사용한 함수에 대한 설명
- isalnum() : 영문자, 숫자 여부를 판별하는 함수이다. 모든 문자를 일일이 점검한다.
- append(char) : append는 list 맨 마지막에 요소를 추가한다.
- lowr() : 소문자로 변환해주는 메서드
- Code에 대한 설명비교를 위해 전처리로 문자를 리스트 매핑하는 방법을 선택하였다.
- 두 번째 for 문은 전체 문자열 길이가 아닌 1/2 로 줄였다. 처음과 각 끝의 문자만 비교하면 되기 때문.
- LeetCode 에서 돌려보고 측정한 속도와 메모리 소비
- Runtime: 52 ms
- Memory Usage: 19.6 MB
2. 해답 풀이 3 가지
아래 세 개의 풀이는 책에서 해답으로 올린 풀이이다.
# 책의 풀이 1
# Runtime: 316 ms, faster than 5.27% of Python3 online submissions for Valid Palindrome.
# Memory Usage: 19.5 MB, less than 12.74% of Python3 online submissions for Valid Palindrome.
def isPalindrome_1(s:str)->bool:
strs=[]
for char in s:
if char.isalnum():
strs.append(char.lower())
# 팰린드로 여부 판별
while len(strs)>1:
if strs.pop(0)!=strs.pop():
return False
return True
- 사용한 메서드에 대한 설명pop() 함수는 마지막 값을 삭제하고 삭제한 값을 return한다. 괄호 안에 인덱스를 지정할 수 있어서 pop(0)으로 지정하면 맨 앞의 값을 가져온다.
- Code에 대한 설명위의 풀이는 1번의 풀이와 비슷하다. 다만 팰린드롬 판별 여부에 for 문이 아닌 while 문을 사용했다는 점과 pop(0), pop()를 사용해 앞의 문자와 뒤의 문자를 제거하면서 비교했다.
- pop(0)은 빅오 O(n)이고, n번 반복하면O(n2)O(n^2) 이 된다 .
- LeetCode 에서 측정한 속도와 메모리 소비
- Runtime: 316 ms
- Usage: 19.5 MB
import collections
from typing import Deque
# 책의 풀이 2 --> 데크사용
# Runtime: 84 ms, faster than 10.63% of Python3 online submissions for Valid Palindrome.
# Memory Usage: 19.3 MB, less than 15.54% of Python3 online submissions for Valid Palindrome.
# 자요현 데크를 선언한다.
def ispalindrome_2(s:str)->bool:
strs:Deque=collections.deque()
for char in s:
if char.isalnum():
strs.append(char.lower())
while len(strs)>1:
if strs.popleft()!=strs.pop():
return False
return True
- 사용한 메서드에 대한 설명데크 자료형을 선언하여 최적화 하였다.
Collections - 컨테이너형
- 이 모듈은 파이썬의 특수 컨테이너 데이터형을 구현한다. [참고자료]
- Code에 대한 설명strsLDeque=collections.deque() 로 데크 자료형을 선언하였다. 데트의 popleft()는 O(1)로 n번 반복하면 O(n)으로 위에서 봤던 pop()과 성능차이가 매우 크다.
- LeetCode 에서 측정한 속도와 메모리 소비
- Runtime: 84 ms
- Memory Usage: 19.3 MB
import re
# 책의 풀이 3 -> 파이썬의 최적화된 내부 기능 사용 -> 슬라이스 & 정규식 이용
# Runtime: 55 ms, faster than 32.89% of Python3 online submissions for Valid Palindrome.
# Memory Usage: 15.7 MB, less than 20.09% of Python3 online submissions for Valid Palindrome.
def isPalindrome_3(s:str)->bool:
s=s.lower()
s=re.sub('[^a-z0-9]', "", s)
return s==s[::-1]
- 사용한 메서드에 대한 설명
- import re : 파이썬에서 정규표현식을 사용할 때 내장 모듈인 re를 사용하고있다.
- re.sub : re.sub（정규 표현식, 대상 문자열 , 치환 문자）
- 문자열 slice 파이썬의 문자열 조작 기능이다.
- Code에 대한 설명앞의 풀이들은 isalnum()으로 모든 문자를 일일이 점검하며 불필요한 문자를 필터링 하였다.또한 슬라이싱으로 [::-1]로 문자를 쉽게 뒤집어 원래 문자와 비교 함으로써 코드 또한 더욱 간결해졌다.
- 내부족으로 C로 빠르게 구현되어있기 때문에 더욱 빠른 속도를 기대할 수 있다.
- 하지만, 위의 코드는 문자열 전체를 한 번에 영숫자(alphanumeric)만 걸러내도록 정규식으로 처리했다.
- LeetCode 에서 측정한 속도와 메모리 소비
- Runtime: 55 ms,
- Memory Usage: 15.7 MB
3. 속도 , 메모리 사용 비요 - 속도, 메모리 사용 비교
풀이 번호 Runtime Memory Useage 1 My 풀이 52 ms 19.6MB 2 책 풀이 1 : 리스트로 변환 316 ms 19.5 MB 3 책 풀이 2 : 데크자료형 84 ms 19.3MB 4 책 풀이 3 : 슬라이싱 사용 55 ms 15.7MB
비교를 해봐도 파이썬의 문자열 조작 메서드를 사용한 방식이 속도나 메모리 사용에서 매우 월등함을 알 수 있다.
(My 풀이는 아무래도 반복을 1/2로 줄여서 속도는 빠른 것 같다)
4. 문자열 슬라이싱
Python에서 문자열 슬라이싱은 매우 빠르게 동작한다. 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되고, 이를 통해 연결된 객체를 찾아 실제 값을 찾아낸다. 이 과정은 매우 빠르게 진행된다.
이런 장점으로 인해 문자열을 조작할 때에는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리하다고 한다 .
표 6-1 슬라이싱을 기준으로 한 파이썬 문자열 처리시간
| 알고리즘 | 실행 시간 | 슬라이싱을 1로 했을 때의 비율 |
|---|---|---|
| 슬라이싱 | 0.499 ms | 1 |
| 리스트 reverse() | 2.46 ms | 5 |
| reversed() + join() | 2.49 ms | 6 |
| for 반복 | 5.5 ms | 12 |
| while 반복 | 9.4 ms | 21 |
| 재귀 | 24.3 ms | 54 |
파이썬은 a=b와 같은 형태로 할당을 하면 변수의 값이 아닌 a변수라 b를 참조 한는 형태가 된다. 따라서 참조가 아닌 값의 복사를 하기 이해 a=b[:] 를 사용한다 (0~마지막 인덱스) 까지 slicing 하는 방식이다.
이러한 방식은 문자열 이나 리스트 를 복사하는 "파이썬 다운" 방식 Pythonic Way 이기도 하다.
Uploaded by Notion2Tistory v1.1.0