[Python] Algorithm #02: 문자열

문자열 탐색, 패턴 매칭, 아나그램, 회문, 투 포인터 등 문자열을 다루는 다양한 알고리즘을 정리했습니다.

---

1. 문자열 탐색

문자열에서 특정 문자나 패턴을 찾는 기본적인 방법입니다.

 

파이썬에서는 find(), in 연산자, index() 등을 활용할 수 있습니다.

실제 문제에서는 여러 번 등장하는 경우 모든 위치를 찾거나, 부분 문자열의 개수를 세는 등으로 확장할 수 있습니다.

s = "hello world"

print(s.find("world"))  # 6 (찾으면 시작 인덱스, 없으면 -1)
print("wor" in s)       # True (포함 여부)

# 여러 번 등장하는 모든 위치 찾기
target = "l"

positions = [i for i, c in enumerate(s) if (c == target)]
print(positions)  # [2, 3, 9]

# 부분 문자열 개수 세기
print(s.count("l"))  # 3

---

2. 패턴 매칭

문자열 내에서 특정 패턴(부분 문자열)이 어디에 등장하는지 효율적으로 찾는 알고리즘입니다.

단순히 find()로도 찾을 수 있지만, KMP, Rabin-Karp 등 고급 알고리즘은 긴 문자열과 패턴에서 빠른 탐색이 가능합니다.

 

실전 코딩테스트에서는 내장 함수로도 충분하지만, 알고리즘 원리를 이해해두면 좋습니다.

s = "ababcababc"
pattern = "abc"

print(s.find(pattern))  # 2

# 모든 패턴 등장 위치 찾기
positions = []
start = 0

while True:
    idx = s.find(pattern, start)
    
    if (idx == -1):
        break
        
    positions.append(idx)
    
    start = idx + 1
    
print(positions)  # [2, 7]

---

3. 아나그램(Anagram)

아나그램은 두 문자열이 문자 구성은 같지만 순서만 다른 경우를 의미합니다.

 

예를 들어 'listen'과 'silent'처럼, 각 문자의 개수가 모두 같으면 아나그램입니다.

 

문자열을 정렬하거나, 딕셔너리/Counter로 문자 개수를 비교하는 방식이 자주 쓰입니다.

a = "listen"
b = "silent"

print(sorted(a) == sorted(b))  # True

---

4. 회문(Palindrome)

회문은 앞에서부터 읽으나 뒤에서부터 읽으나 같은 문자열을 의미합니다.

예를 들어 'level', 'racecar' 등이 있습니다.

 

문자열을 뒤집어서 비교하거나, 투 포인터로 양쪽에서 비교하는 방식이 있습니다.

 

회문 판별은 문자열 문제에서 자주 등장하는 기본 패턴입니다.

s = "level"

print(s == s[::-1])  # True

# 대소문자 구분 없이 회문 판별
word = "RaceCar"

print(word.lower() == word.lower()[::-1])  # True

---

5. 투 포인터(Two Pointer)

투 포인터는 리스트나 문자열에서 두 개의 인덱스를 사용해 효율적으로 문제를 푸는 기법입니다.

정렬된 배열에서 합이 특정 값이 되는 쌍 찾기, 회문 판별, 구간 합 등 다양한 문제에 활용됩니다.

 

양쪽 끝에서 시작해 가운데로 이동하거나, 한쪽 포인터는 고정하고 다른 한쪽만 이동시키는 등 다양한 변형이 있습니다.

s = "abccba"
left, right = 0, len(s) - 1
is_palindrome = True

while (left < right):
    if (s[left] != s[right]):
        is_palindrome = False
        
        break
        
    left += 1
    right -= 1
    
print(is_palindrome)  # True

# 투 포인터로 부분합 구하기 예시
arr = [1, 2, 3, 2, 5]

sum_target = 5
left = right = total = 0
count = 0
n = len(arr)

while True:
    if (total >= sum_target):
        total -= arr[left]
        left += 1
        
    elif (right == n):
        break
        
    else:
        total += arr[right]
        right += 1
        
    if (total == sum_target):
        count += 1
        
print(count)  # 3 ([2,3], [3,2], [5])