두 개의 문자열 word0, word1과 하나의 텍스트가 주어졌을 때, 텍스트 안에서 두 단어가 등장하는 위치 사이의 최소 거리를 찾는 문제를 살펴보겠습니다. 여기서 거리는 두 단어 사이에 있는 단어의 개수로 측정하며, 만약 두 단어 중 하나라도 텍스트에 존재하지 않으면 -1을 반환해야 합니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
- text = "cat dog abcd dog cat cat abcd dog wxyz"
- word0 = "abcd"
- word1 = "wxyz"
이 경우 출력은 1입니다. "abcd"와 "wxyz" 사이에 정확히 한 단어("dog")만 존재하기 때문입니다.
문제 해결 접근 방식
이 문제는 텍스트를 한 번만 순회하면서 해결할 수 있습니다. 핵심 아이디어는 대상 단어(word0 또는 word1)를 발견할 때마다 이전에 발견한 위치와 비교하여 서로 다른 단어라면 그 사이의 거리를 계산하는 것입니다.
구체적인 알고리즘은 다음과 같습니다.
- 텍스트를 공백 기준으로 분리하여 단어 리스트(word_list)를 만듭니다.
- 정답 변수(ans)를 단어 리스트의 크기로 초기화합니다. 이 값은 가능한 최대 거리보다 큰 값으로, "두 단어가 모두 발견되지 않았음"을 나타내는 플래그 역할도 합니다.
- 이전 대상 단어의 인덱스를 저장할 L을 null로 초기화합니다.
- R을 0부터 리스트 끝까지 순회하며 다음을 수행합니다.
- 현재 단어가 word0 또는 word1이라면:
- L이 이미 설정되어 있고, 현재 단어가 L 위치의 단어와 다르다면(즉 서로 다른 두 대상 단어라면), ans를 min(ans, R - L - 1)로 갱신합니다.
- L을 R로 갱신합니다.
- 현재 단어가 word0 또는 word1이라면:
- 순회가 끝난 후 ans가 초기값(리스트 크기)과 같으면 -1을 반환하고, 그렇지 않으면 ans를 반환합니다.
이 방법은 텍스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 효율적으로 동작합니다.
파이썬 구현 예제
class Solution: def solve(self, text, word0, word1): word_list = text.split() ans = len(word_list) L = None for R in range(len(word_list)): if word_list[R] == word0 or word_list[R] == word1: if L is not None and word_list[R] != word_list[L]: ans = min(ans, R - L - 1) L = R return -1 if ans == len(word_list) else ans ob = Solution() text = "cat dog abcd dog cat cat abcd dog wxyz" word0 = "abcd" word1 = "wxyz" print(ob.solve(text, word0, word1))
입력
"cat dog abcd dog cat cat abcd dog wxyz", "abcd", "wxyz"
출력
1
코드 설명
text.split()은 텍스트를 공백을 기준으로 나누어 단어 리스트를 생성합니다. 순회 과정에서 현재 단어가 word0 또는 word1에 해당하면, 이전에 기록해 둔 위치 L과 비교합니다. 두 위치의 단어가 서로 다른 대상 단어일 때만 거리(R - L - 1)를 계산하여 최솟값을 갱신합니다. 같은 단어가 연속해서 등장하는 경우에는 거리를 계산하지 않고 L의 위치만 최신화합니다.
마지막으로 ans가 초기값인 리스트 전체 길이와 동일하다면 두 단어가 함께 등장한 적이 없다는 의미이므로 -1을 반환하고, 그렇지 않으면 계산된 최소 거리를 반환합니다.