백준/문자열

[백준] 1786번, 찾기 - Python

CoGam 2024. 4. 28. 00:12
728x90

 

 

문제 이해

문제 자체는 정말 단순하다. 긴 문자열이 쭉 주어지고, pattern이라는 짧은 문자열이 주어졌을 때 긴 문자열 안에서 pattern이 몇 번 반복되는지 찾는 문제이다.

 

하지만 단순한 문제에 그렇지 않은 설명 길이를 보면 어려운 문제임을 직감할 수 있다.

 

이 문제가 어려운 이유는 시간 복잡도 때문 일 것이다. 단순히 접근한다면 패턴 길이만큼을 패턴과 같은지 체크하면서 한 칸씩 전진하면 될 것이다. 물론 해결이 가능하지만 문제 설명에 쓰여 있는 것과 같이 시간 복잡도를 만족시킬 수 없다.

더 효율적인 코드가 필요하고, 이를 위한 대표적인 문자열 알고리즘으로는 Boyer-Moore, Rabin-Karp, KMP 등이 있다.

 

그 중에서 이번에는 KMP 알고리즘으로 문제를 해결해보자.

 

 

실제 코드

def failNaive(pattern):     # 실패함수 주의해서 짜기
    result = [0 for _ in range(len(pattern))]
    i = 0
    j = 1
    while j < len(pattern):
        if pattern[i] == pattern[j]:
            i += 1
            result[j] = i
            j += 1
        else:
            if i != 0:
                i = result[i - 1]
            else:
                result[j] = 0
                j += 1
    return result


def kmp(text, pattern):
    result = []
    posT = 0
    posP = 0
    f = failNaive(pattern)
    while posT < len(text):
        if text[posT] == pattern[posP]:
            posT += 1
            posP += 1
            if posP == len(pattern):
                result.append(posT - posP + 1)
                posP = f[posP - 1]     # 그냥 0으로 보내면 스킵하게 되는 부분 생김
        else:
            if posP == 0:    # 왜 posT로 두면 안될까?
                posT += 1
            else:
                posP = f[posP - 1]

    return result


text = input()
pattern = input()

result = kmp(text, pattern)
print(len(result))
for i in result:
    print(i, end=" ")

 

 

해설

KMP 알고리즘은 크게 두 가지 함수로 구성된다.

첫째는 흔히 실패함수 라고 불리고 두 번째는 kmp함수이다.

 

먼저 실패함수를 이해해야한다. 이전에 살펴본 브루트포스 한 방식의 풀이는 어떤 경우에도 한 문자씩 전진하며 패턴과의 일치 여부를 판단했다. 하지만 패턴 안에 중복되는 문자열이 있는 경우 이 전진하는 단위를 더욱 늘릴 수 있을 것이라는 아이디어가 생겨난 것이다. 이것이 KMP 알고리즘의 기반이다. 아래 그림을 보면 조금 이해가 편할 것 같다.

 

 

각 단계별로 위에 있는 것이 긴 문자열, 아래 있는 것이 pattern이다. 1번 단계에서 검사를 하다보니 마지막 문자만 자르고 모두 같은 것을 알 수 있다. 아쉽다는 생각에서 끝나면 안된다. 검사를 통해 우리에게 정보가 주어진 것이다. 블랙박스 같던 긴 문자열에 우리가 아는 값들이 생긴 것이다. 정보를 얻었으면 적절히 이용해야한다.

 

pattern을 보니 시작하는 부분의 AB와 중반부에 있는 AB가 반복이 일어나는 최대 문자열인 것을 알 수 있다 (그 사이에는 시작 부분과 겹치는 부분이 없다). 즉 긴 문자열을 만족시킨 부분 중, pattern의 접두사와 접미사를 확인하여 최대로 반복 가능한 구간을 찾아낸 것이다. 그렇게 하면 브루트포스처럼 한 칸 전진이 아니라, 한 번에 여러 칸을 전진시킬 수 있는 확실한 근거가 찾아지는 것이다.

 

그리고 이것을 가능하게 만들어주는 것이 pattern의 pattern을 찾는 알고리즘, 즉 실패함수를 만드는 것이다 (위의 그림에서는 pattern 아래에 적힌 숫자 표가 그것이다).

 

 

두 번째로 kmp 함수를 살펴보자. 이제는 pattern과 긴 문자열 각각의 인덱스를 비교하며 같은 구간을 찾는다.

 

이제 달랐을 때에 집중해야한다.

  1. pattern의 인덱스가 0번째였을 경우에는 긴 문자열만 하나 전진시키면 된다.
  2. pattern의 인덱스가 0번째가 아닌 경우는, 그냥 0으로 옮기는 것이 아닌 pattern의 반복 구간을 고려해서 최적의 위치로 posP를 이동시킨다. 즉 실패함수를 이용한다.

같은 경우에는 원래의 경우라면 pattern과 긴 문자열의 인덱스를 같이 전진시키면 된다. 하지만 이 문제의 특성상 몇 번 반복인지 찾는 것이기 때문에, 반복되는 것을 한 번 찾더라도 다시 다음 패턴을 찾을 준비를 해야한다.

  1. 이 부분이 가장 어려웠는데, 이때도 posP를 바로 0으로 가면 스킵하게 되는 부분이 생긴다. 따라서 실패함수를 이용해야한다.

 

 

실버 문제들도 힘겹게 풀던 시절 이 문제를 접했다. 무식하게 풀어보려 했던 것은 아니고 자료구조 수업 시간에 해당 알고리즘을 배우게 되면서 연습삼아 풀었던 것이다. 그때부터 지금까지 내가 풀었던 문제 중 아직까지는 가장 어려웠던 문제 같다. 당시에도 3시간을 고민하다가 종이에 직접 과정을 하나하나 써가면서 겨우 이해했던 것 같다. 하지만 일주일 정도 지났을까, 이해했던 부분을 놓쳐서 또 고생을 하였다. 부지런히 공부해야하는 이유를 깨닫게 해주는 문제였다.

반응형