파이썬 코딩테스트 강좌, 문자열 찾기

안녕하세요! 오늘은 코딩테스트 준비를 위한 문자열 찾기 문제를 다뤄보겠습니다. 문자열 찾기 문제는 기본적으로 문자열에서 특정 패턴이나 서브 문자열을 찾는 알고리즘 문제입니다. 이러한 문제는 효율성, 정확성, 그리고 다양한 방법론을 테스트하여 실제 코딩테스트 상황에서 어떻게 접근할지에 대한 이해를 높이는 것이 중요합니다.

문제 설명

당신은 문자열 s와 문자열 t가 주어졌을 때, 문자열 s에서 문자열 t가 몇 번 등장하는지 계산하는 함수를 작성해야 합니다. 이때, 문자열 t가 겹칠 수 있다는 점에 유의하세요.

예제 입력:

    s = "abababab"
    t = "aba"

예제 출력:

문제 접근 방법

이 문제를 해결하기 위해서는 다음과 같은 접근 방법을 사용할 수 있습니다:

슬라이딩 윈도우 방법: 문자열을 슬라이딩 윈도우처럼 이동하면서 탐색할 수 있습니다.
문자열 탐색 알고리즘: KMP 알고리즘과 같은 문자열 탐색 알고리즘을 사용할 수 있습니다.

슬라이딩 윈도우 접근

슬라이딩 윈도우 방법을 이용하여 이 문제를 푸는 과정을 설명하겠습니다. 이 방법은 단순하지만 효율적인 해결책을 제공할 수 있습니다.

슬라이딩 윈도우 방법의 기본 아이디어는 주어진 문자열 s를 탐색하며 각 위치에서 문자열 t와 비교하는 것입니다. 대략적인 단계는 다음과 같습니다:

변수 count를 초기화하여 발견된 패턴의 개수를 저장합니다.
문자열 s의 각 인덱스에서 반복문을 실행합니다.
각 반복에서, 문자열 s의 현재 인덱스부터 len(t) 만큼의 부분 문자열을 가져옵니다.
가져온 부분 문자열과 t를 비교합니다.
일치할 경우 count를 증가시킵니다.
문자열 s의 모든 인덱스를 탐색한 후 count를 반환합니다.

파이썬 코드 구현

위의 접근 법을 바탕으로 Python 코드를 작성해 보겠습니다:


def count_occurrences(s, t):
    count = 0
    t_len = len(t)
    s_len = len(s)

    for i in range(s_len - t_len + 1):
        if s[i:i + t_len] == t:
            count += 1

    return count

# 예시 테스트
s = "abababab"
t = "aba"
result = count_occurrences(s, t)
print("문자열 '{}'에서 '{}'의 등장 횟수: {}".format(s, t, result))

시간 복잡도 분석

위의 코드에서 가장 큰 O(n * m)이라는 시간 복잡도를 가지며, 여기서 n은 문자열 s의 길이, m은 문자열 t의 길이입니다. 그러나 이 구현은 단순한 문자열 비교를 기반으로 하므로 최악의 성능을 가질 수 있습니다.

KMP 알고리즘을 이용한 해결 방법

슬라이딩 윈도우 방법 이외에도, KMP 알고리즘을 사용하여 이 문제를 보다 더 효율적으로 해결할 수 있습니다. KMP 알고리즘은 문자열을 한 번만 탐색하여 패턴 일치를 찾는 선형 시간 알고리즘입니다. 이 알고리즘의 핵심은 패턴에 대한 접두사와 접미사의 정보를 미리 계산하여 일치하지 않는 경우, 패턴을 조금 더 이동할 수 있도록 지원하는 것입니다.

KMP 알고리즘의 기본 단계

패턴 t에 대한 LPS (Longest Prefix Suffix) 배열을 생성합니다.
문자열 s를 탐색하면서 LPS 배열을 참조하여, 문자가 일치하지 않을 경우 몇 칸을 건너뛰어야 하는지 결정합니다.
모든 패턴의 일치를 추적합니다.

LPS 배열 생성 함수

LPS 배열을 생성하기 위해서 다음과 같은 함수를 작성할 수 있습니다:


def compute_lps(pattern):
    length = 0
    lps = [0] * len(pattern)
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length-1]
            else:
                lps[i] = 0
                i += 1
    return lps

KMP 알고리즘 구현

이제 KMP 알고리즘을 기반으로 실제 문자열 찾기 코드를 작성해보겠습니다:


def kmp_search(s, t):
    lps = compute_lps(t)
    count = 0
    i = 0  # 문자열 s의 인덱스
    j = 0  # 패턴 t의 인덱스

    while i < len(s):
        if s[i] == t[j]:
            i += 1
            j += 1

        if j == len(t):
            count += 1
            j = lps[j-1]
        elif i < len(s) and s[i] != t[j]:  # 매치 실패
            if j != 0:
                j = lps[j-1]
            else:
                i += 1

    return count

# 예시 테스트
s = "abababab"
t = "aba"
result = kmp_search(s, t)
print("문자열 '{}'에서 '{}'의 등장 횟수: {}".format(s, t, result))

결론

오늘 우리는 문자열 찾기 문제를 슬라이딩 윈도우와 KMP 알고리즘을 통해 해결해보았습니다. 슬라이딩 윈도우 방법은 직관적이고 간단하지만, KMP 알고리즘은 보다 효율적인 방법을 제공합니다. 이러한 알고리즘을 이해하고 활용하는 것은 코딩테스트에서 좋은 성적을 얻는 데 큰 도움이 됩니다.

여러분들도 다양한 문제를 통해 이러한 알고리즘을 익히셔서 코딩테스트에 자신감을 가지시길 바랍니다!