[ Python_Algorithm ] 문자열 조작 1

황승환·2022년 1월 6일

Python_Algorithm

목록 보기

4/32

문자열 조작

문자열 조작이란 문자열을 변경하거나 분리하는 등의 여러 과정을 말한다. 대부분의 언어에서는 별도의 문자열 자료형과 문자열을 조작하기 위한 다양한 기능들을 기본적으로 제공하고 있기 때문에 굳이 제약을 두지 않는 한 언어에서 제공하는 기본 기능들을 잘 활용하는 편이 가장 좋다. 문자열 조작은 다음과 같은 분야에서 대표적으로 사용된다.

정보 처리 분야
어떤 키워드로 웹 페이지를 탐색할 때 문자열 처리 애플리케이션을 이용하게 된다. 특히 현대의 거의 모든 정보는 문자열로 구성되어 있으며 문자열 처리는 정보 처리에서 핵심적인 역할을 한다.
통신 시스템 분야
문자 메시지나 이메일을 보낼 때 기본적으로 문자열을 어느 한 곳에서 다른 곳으로 보내게 된다. 이처럼 데이터 전송은 문자열 처리 알고리즘이 탄생한 기원이기도 하며 데이터 전송에서 문자열 처리는 매우 중요한 역할을 한다.
프로그래밍 시스템 분야
프로그램은 그 자체가 문자열로 구성되어 있다. 컴파일러나 인터프리터 등은 문자열을 해석하고 처리하여 기계어로 변환하는 역할을 하며 여기에는 매우 정교한 문자열 처리 알고리즘 등이 쓰인다.

LeetCode 125.Valid Palindrome

주어진 문자열이 펠린드롬인지 확인하라. 대소문자를 구분하지 않으며 영문자와 숫자만을 대상으로 한다.

Solution 1 리스트로 변환

주어진 문자열을 문자열로 변환하여 해결하는 방법이다. 문자열을 순회하며 문자열의 각 문자가 알파벳이거나 숫자일 경우 (isalnum() 사용) 만들어 놓은 리스트에 해당 문자를 소문자로 변환하여 추가한다. 그리고 리스트의 가장 앞과 가장 뒤의 문자를 비교하며 서로 다를 경우 False를 반환하고 while문을 끝까지 수행한 경우 True를 반환한다.

class Solution:
    def isPalindrome(self, 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

런타임이 276ms 걸린 것을 확인할 수 있다.

Solution 2 데크 자료형을 이용한 최적화

Solution 1과 비슷한 방법이지만 strs를 배열이 아닌 Deque로 명시적으로 선언해주어 해결하는 방법이다. 데크를 사용한 이유는 리스트의 pop(0)은 O(n)이지만 데크의 popleft()은 O(1)이기 때문이다. Solution 1은 총 시간 복잡도가 O(n^2)이고 데크를 활용한 이번 Solution은 O(n)이다.

class Solution:
    def isPalindrome(self, 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

O(n^2) -> O(n)으로 시간 복잡도가 향상됨에 따라 런타임이 70ms로 줄었다.

Solution 3 슬라이싱 사용

이번 풀이는 별 다른 알고리즘 없이 정규식으로 불필요한 문자를 필터링하고 슬라이싱 기법을 통해 원래의 문자열과 거꾸로 뒤집은 문자열을 비교하여 반환하였다. 반복문도 없고 슬라이싱은 내부적으로 C로 돌아가기 때문에 가장 빨랐다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s=s.lower()
        s=re.sub('[^a-z0-9]', '', s)
        return s==s[::-1]

런타임이 32ms로 가장 짧았다.

문법: 문자열 슬라이싱

파이썬은 문자열 슬라이싱이라는 매우 편리한 기능을 제공한다. 내부적으로 빠르게 동작한다는 점이 인상적이다. 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 찾아내는데 이 과정은 매우 빠르게 진행되므로 문자열을 조작할 때는 항상 슬라이싱을 우선적으로 사용하는 편이 속도 개선에 유리하다. 문자열을 별도로 매핑하는 방법도 좋은 방법이지만 이 과정에서 상당한 연산 비용이 들기 때문에 전체적인 속도에서 손해를 볼 수 있다.

슬라이싱			0.499ms
리스트 reverse()		2.46ms
reversed()+join()	2.49ms
for 반복			5.5ms
while 반복		9.4ms
재귀			24.3ms

이처럼 슬라이싱은 파이썬이 제공하는 기능 중 속도가 가장 빠르면서도 매우 편리하게 사용할 수 있다.

0  1  2  3  4
H  e  l  l  o
-5 -4- 3- 2 -1

s = 'Hello'
s[1:3] # el. 인덱스 1부터 3 이전까지 표현한다. (3은 포함 X)
s[1:-2] # el. 인덱스 1부터 -2 이전까지 표현한다. (-2는 포함 X)
s[1:] # ello. 인덱스 1부터 끝까지 표현한다.
s[:] # Hello. 전체를 표현한다.
s[1:100] # ello. 인덱스가 지나치게 클 경우에는 최대 길이만큼만 표현한다.
s[-1] # o. 마지막 문자(뒤에서 첫번째)
s[-3] # l. 뒤에서 세번째
s[:-3] # He. 처음부터 뒤에서 세번째 이전까지
s[::1] # Hello. 1은 기본값으로 원본과 동일
s[::-1] # olleH. 뒤집는다.

LeetCode 344.Reverse String

문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라.

Solution 1 투 포인터를 이용한 스왑

말 그대로 가장 왼쪽과 가장 오른쪽을 가리키는 포인터를 각각 사용하여 이들을 증가시키고 감소시키며 두 자리를 바꿔주어 문자열을 뒤집는 방법이다.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left, right = 0, len(s)-1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left+=1
            right-=1

310ms가 소요된 것을 확인할 수 있다.

Solution 2 파이썬다운 방식

이 문제를 파이썬다운 방식으로 풀이하면 한줄로 풀이가 가능하다. 입력값이 리스트이므로 reverse() 함수를 사용하면 바로 뒤집을 수 있다.

class Solution:
    def reverseString(self, s: List[str]) -> None:
       s.reverse()

263ms가 소요되었다. 이번 문제는 슬라이싱을 통해서도 해결할 수 있지만 LeetCode에서는 에러를 발생시킨다. 플랫폼마다 제약이 서로 다르기 때문에 이러한 부분들을 코딩 테스트 전에 미리 숙지하는 것도 중요하다.

LeetCode 937.Reorder Log Files

로그를 재정렬하라. 기준은 다음과 같다
1. 로그의 가장 앞 부분은 식별자다.
2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다.
3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다.
4. 숫자 로그는 입력 순서대로 한다.

Solution 1 람다와 + 연산자를 이용

요구 조건을 얼마나 깔끔하게 처리할 수 있는지를 묻는 문제로 실무에서도 이와 같은 로직은 자주 쓰이는 만큼 매우 실용적인 문제라고 할 수 있다. 문자로 구성된 로그는 숫자 로그 이전에 오고, 숫자 로그는 입력 순서대로 들어가야 하므로 문자 로그만 저장하는 배열과 숫자 로그만 저장하는 배열을 따로 구성하고 sort() 함수에 람다식을 넣어 식별자를 제외한 나머지로 정렬할 수 있도록 작성하였다.

람다 표현식은 다음과 같이 작성하였다.

letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))

식별자를 제외한 문자열 [1:]을 키로 하여 정렬하고 동일한 경우 후순위로 식별자 [0]를 지정해 정렬하도록 하는 람다식이다.

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        letters, digits = [], []
        for log in logs:
            if log.split()[1].isdigit():
                digits.append(log)
            else:
                letters.append(log)
        letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))
        return letters+digits