[개념] 문자열

개념

- 문자열 조작이란 문자열을 변경하거나 분리하는 등의 여러 과정을 의미
- 문자열은 로우 레벨에서 조작하거나, 문자형이 따로 없는 C 같은 경우 조작이 매우 까다로움
- 대부분의 언어에서는 문자열 조작을 위한 다양한 기능을 기본으로 제공하므로 기본 기능들을 잘 활용하는 것이 중요

문자열 처리가 사용되는 분야

1) 정보 처리 분야: 현대의 거의 모든 정보는 문자열로 구성되어 있어, 문자열 처리는 정보 처리에 핵심적인 역할을 한다.
2) 통신 시스템 분야: 메세지, 이메일 전송 시 문자열을 한곳에서 다른 한 곳으로 전송한다. 또한 데이터 전송은 문자열 처리 알고리즘이 탄생한 배경이기도 하다.
3) 프로그래밍 시스템 분야: 프로그램은 자체가 문자열로 구성되어져 있다.

예제1 유효한 팰린드롬_ from leetcode 125 (valid Palindrome)

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Constraints:

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

팰린드롬이란 앞뒤가 똑같은 단어, 문장을 의미한다. 즉, 뒤집어도 같은 말이 되는 단어, 문장을 팰린드롬이라고 한다.

풀이1_리스트로 변환

직접 문자열을 입력받아 팰린드론 여부를 판별한다. 이 문제에서는 대소문자를 구분하지 않는다는 점을 유의해야 한다.

1) 전처리

strs = []
for char in s:
    if char.isalnum():
        stars.append(char.lower())

- isalnum() : 영문자 숫자 여부를 판별하는 함수.
- char.lower() : 모든 문자를 소문자로 변환.

이 문제에서는 리스트의 문자열 원소를 하나씩 순회하며 , 문자가 영문자, 숫자 인지 판별한다.
조건문의 값이 True 가 되면 문자를 새로운 list strs에 소문자로 1개씩 추가한다.

2) 팰린드롬 여부 판별

while len(stars) > 1:
    if strs.pop(0) != strs.pop():
        return False

파이썬의 list는 pop() 함수에서 index 지정이 가능하다.
따라서, 반복문을 돌며 맨 앞 부분 pop(0) 과 맨 뒷 부분 pop() 의 원소가 같지 않으면 False를 반환한다.

풀이2_deque 사용

앞선 풀이1로도 충분히 문제 해결이 가능하지만, deque 자료형을 사용하면 수행 속도를 향상 시킬 수 있다.

from collections import deque

# 풀이1의 list를 deque로 선언
strs = deque([])

for char in s:
    if char.isalnum():
        stars.append(char.lower())

앞선 list를 사용한 풀이1의 실행 속도는 304(ms)에 반하여, deque를 사용하면 실행 속도가 64(ms)까지 줄어든다.
풀이1에 비하여 5배 가까운 속도 향상을 보여 준다.

list의 pop(0)의 빅오가 O(n)인 것에 반해, deque의 popleft()는 O(1)이기 때문에,
n번씩 반복 시행 하였다고 가정하면, 각각 O(n**2), O(n)으로 성능 차이가 크게 발생한다.

풀이3_Slicing