파이썬으로 텍스트 내 두 단어 사이의 최소 거리 찾는 프로그램

문제 개요

세 개의 문자열 text, w1, w2가 주어졌다고 가정해 봅시다. text는 여러 단어로 이루어진 문장입니다. 우리가 구해야 할 것은 text 안에서 w1과 w2가 등장하는 모든 위치 조합 중 가장 짧은 거리이며, 거리는 두 단어 사이에 끼어 있는 단어의 개수로 측정합니다. 만약 w1 또는 w2가 text에 존재하지 않는다면 -1을 반환해야 합니다.

예를 들어 입력이 다음과 같다고 해보겠습니다.

• text = "joy happy power happy joy joy power happy limit"
• w1 = "power"
• w2 = "limit"

이 경우 출력은 1이 됩니다. "power"와 "limit" 사이에는 "happy"라는 단어 딱 하나만 존재하기 때문입니다.

알고리즘 접근 방법

이 문제는 문장을 한 번만 순회하면서 두 단어의 가장 최근 등장 위치를 추적하면 효율적으로 해결할 수 있습니다. 구체적인 절차는 다음과 같습니다.

• index1 := null, index2 := null 로 초기화합니다.
• distance := 999999 와 같이 충분히 큰 값으로 초기화합니다.
• text의 각 인덱스 idx와 단어 w에 대해 반복합니다.
  • w가 w1과 같으면:
    • index2가 null이 아니라면, distance := distance와 (|idx − index2| − 1) 중 더 작은 값으로 갱신합니다.
  • index1 := idx 로 갱신합니다.
• w가 w2와 같으면:
  • index1이 null이 아니라면, distance := distance와 (|idx − index1| − 1) 중 더 작은 값으로 갱신합니다.
• index2 := idx 로 갱신합니다.

여기서 |idx − index| − 1 은 두 단어 사이에 있는 단어의 개수를 의미합니다. 반대 순서(w2가 먼저 나오고 w1이 나중에 나오는 경우)도 고려되므로, 어떤 단어가 먼저 등장하더라도 올바른 최소 거리를 구할 수 있습니다.

구현 예제

아래 구현 예제를 통해 동작 방식을 더 잘 이해해 보겠습니다.

def solve(text, w1, w2):
    index1 = None
    index2 = None
    distance = 2000000
    for idx, word in enumerate(text.split(" ")):
        if word == w1:
            if index2 is not None:
                distance = min(distance, abs(idx - index2) - 1)
            index1 = idx
        if word == w2:
            if index1 is not None:
                distance = min(distance, abs(idx - index1) - 1)
            index2 = idx
    if index1 is not None and index2 is not None:
        return distance
    return -1

text = "joy happy power happy joy joy power happy limit"
w1 = "power"
w2 = "limit"
print(solve(text, w1, w2))

입력

"joy happy power happy joy joy power happy limit", "power", "limit"

출력

1

마무리

이 알고리즘은 문장을 단 한 번의 순회(O(n))로 처리하면서 항상 두 단어의 가장 최근 위치만 기억하기 때문에 매우 효율적입니다. 검색 엔진이나 문서 분석 도구에서 특정 키워드 간 근접성(proximity)을 평가할 때 자주 활용되는 기법이니, 직접 다양한 입력으로 테스트해 보며 동작 원리를 익혀 보시기 바랍니다.