문자열 (String) 자료구조

개요

문자열(String)은 문자(character)들의 연속된 시퀀스를 나타내는 자료구조로, 텍스트 데이터를 저장하고 처리하는 데 사용됩니다. 대부분의 프로그래밍 언어에서 문자열은 문자 배열(Array of characters)의 형태로 구현됩니다.

문자열은 불변(immutable)한 경우가 많아, 한 번 생성되면 내용을 변경할 수 없는 특징을 가지며, 다양한 문자열 처리 알고리즘이 존재합니다.

---

문자열의 특징

1. 연속된 메모리 공간 사용

   • 배열과 마찬가지로, 문자열도 연속적인 메모리 공간에 저장됩니다.
   • 따라서 특정 인덱스에 있는 문자에 $O(1)$의 시간 복잡도로 접근할 수 있습니다.

2. 불변성 (Immutable)

   • 대부분의 언어에서 문자열은 불변(Immutable)합니다. 즉, 한 번 생성된 문자열은 변경할 수 없습니다.
   • 만약 문자열을 변경하고 싶다면, 새로운 문자열을 생성해야 합니다.

3. 길이 연산의 시간 복잡도

   • 문자열의 길이(len(str))를 구하는 연산은 $O(1)$입니다.
   • 이유는 문자열이 생성될 때 길이를 함께 저장하기 때문입니다.

4. 문자열 연결 (Concatenation) 연산의 비용

   • 문자열을 단순히 + 연산자로 연결하면 새로운 문자열이 생성되므로 $O(n)$의 비용이 발생합니다.
   • 따라서 여러 개의 문자열을 합칠 때는 join()을 사용하는 것이 효율적입니다. ($O(n)$)

---

문자열 연산

1. 접근 (Access) - $O(1)$

문자열의 특정 문자에 접근하는 연산은 배열과 마찬가지로 $O(1)$입니다.

s = "hello"
print(s[1])  # 'e'

---

2. 문자열 탐색 (Search) - $O(n)$

문자열에서 특정 문자 또는 서브 문자열을 찾는 연산입니다.

s = "hello world"
print(s.find("world"))  # 6  (서브 문자열의 시작 인덱스 반환)
print(s.find("python")) # -1 (존재하지 않으면 -1 반환)

• find()는 문자열을 순차 탐색(Linear Search)하므로 시간 복잡도는 $O(n)$입니다.
• 정렬된 문자열에서 이진 탐색을 사용하면 $O(\log n)$의 속도로 찾을 수 있습니다.

---

3. 문자열 비교 (Comparison) - $O(n)$

두 개의 문자열을 비교하는 연산은 문자 하나씩 비교해야 하므로 $O(n)$의 시간 복잡도를 가집니다.

s1 = "apple"
s2 = "banana"
print(s1 == s2)  # False
print(s1 < s2)   # True (사전 순 비교)

• 파이썬에서는 "==", "<", ">" 연산자를 사용하여 문자열을 비교할 수 있습니다.
• 문자열 비교는 ASCII 또는 유니코드 값을 기반으로 합니다.

---

4. 문자열 연결 (Concatenation) - $O(n)$

문자열을 연결하는 연산입니다.

s1 = "hello"
s2 = " world"
print(s1 + s2)  # "hello world"

하지만, 문자열을 여러 번 연결하면 새로운 문자열을 생성해야 하므로 비효율적입니다.
따라서 join()을 사용하는 것이 좋습니다.

words = ["hello", "world", "python"]
print(" ".join(words))  # "hello world python"

• join()은 $O(n)$의 시간 복잡도를 가지며, 문자열을 효율적으로 연결할 수 있습니다.

---

5. 문자열 분할 (Splitting) - $O(n)$

문자열을 특정 구분자를 기준으로 나누는 연산입니다.

s = "apple,banana,grape"
print(s.split(","))  # ['apple', 'banana', 'grape']

• split() 연산은 $O(n)$의 시간 복잡도를 가집니다.

---

6. 문자열 뒤집기 (Reverse) - $O(n)$

문자열을 뒤집는 연산입니다.

s = "hello"
print(s[::-1])  # "olleh"

• 슬라이싱을 사용하면 $O(n)$에 문자열을 뒤집을 수 있습니다.

---

7. 패턴 매칭 (Pattern Matching)

문자열에서 특정 패턴을 찾는 알고리즘입니다.

1) 브루트포스 (Brute Force) - $O(nm)$

• 단순히 문자열을 하나씩 비교하는 방식.

def brute_force_search(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            return i
    return -1

text = "hello world"
pattern = "world"
print(brute_force_search(text, pattern))  # 6

2) KMP 알고리즘 - $O(n)$

• 접두사와 접미사를 활용하여 문자열을 빠르게 검색하는 알고리즘.

def kmp_search(text, pattern):
    def compute_lps(pattern):
        lps = [0] * len(pattern)
        j = 0
        for i in range(1, len(pattern)):
            while j > 0 and pattern[i] != pattern[j]:
                j = lps[j - 1]
            if pattern[i] == pattern[j]:
                j += 1
                lps[i] = j
        return lps

    lps = compute_lps(pattern)
    i = j = 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                return i - j
        else:
            j = lps[j - 1] if j > 0 else 0
            i += 1 if j == 0 else 0
    return -1

text = "hello world"
pattern = "world"
print(kmp_search(text, pattern))  # 6

• KMP 알고리즘은 $O(n)$의 시간 복잡도를 가집니다.

---

문자열 관련 문제 예제

1. 회문 (Palindrome) 판별 - $O(n)$

회문(Palindrome)은 앞에서 읽어도, 뒤에서 읽어도 같은 문자열을 의미합니다.

def is_palindrome(s):
    return s == s[::-1]

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False

---

2. 아나그램 (Anagram) 판별 - $O(n\log n)$ 또는 $O(n)$

아나그램은 단어의 문자를 재배열하여 다른 단어를 만들 수 있는 경우입니다.

def is_anagram(s1, s2):
    return sorted(s1) == sorted(s2)  # O(n log n)

print(is_anagram("listen", "silent"))  # True
print(is_anagram("hello", "world"))    # False

• sorted()를 사용하면 $O(n \log n)$이지만, Counter를 사용하면 $O(n)$으로 최적화할 수 있습니다.

from collections import Counter
def is_anagram_optimized(s1, s2):
    return Counter(s1) == Counter(s2)  # O(n)

print(is_anagram_optimized("listen", "silent"))  # True

---

결론

문자열은 중요한 자료구조로, 여러 알고리즘에서 활용됩니다.
빠른 조회가 가능하지만 불변성(Immutable)으로 인해 문자열 변경이 비효율적일 수 있습니다.
문자열을 다룰 때 join(), split(), 슬라이싱, 패턴 매칭 알고리즘을 적절히 활용하면 효율적으로 문제를 해결할 수 있습니다. 🚀