생성자에서 단어 목록을 전달받아 저장하는 클래스가 있다고 가정해 봅시다. 이 클래스에는 두 단어 word1과 word2를 매개변수로 받아, 리스트 안에서 이 두 단어 사이의 최단 거리를 찾는 메서드가 있습니다. 핵심은 이 메서드가 서로 다른 인자 조합으로 수없이 반복 호출될 수 있다는 점이며, 따라서 호출 시마다 빠르게 결과를 반환하도록 설계해야 합니다.
예를 들어 words = ["practice", "makes", "perfect", "skill", "makes"]라고 가정해 보겠습니다. 이때 입력이 word1 = "skill", word2 = "practice"라면 출력은 3이 됩니다. "skill"은 인덱스 3에, "practice"는 인덱스 0에 위치하므로 두 위치의 차이 |3 − 0| = 3이 바로 정답입니다.
접근 방법
이 문제의 관건은 메서드가 반복적으로 호출된다는 점입니다. 호출할 때마다 전체 리스트를 처음부터 끝까지 훑는 방식은 비효율적입니다. 대신 생성자 단계에서 각 단어가 등장한 모든 인덱스를 해시맵에 미리 저장해 두면, shortest()가 호출될 때 해당 두 단어의 인덱스 목록만 꺼내 비교하면 됩니다.
인덱스는 생성자에서 왼쪽부터 오른쪽으로 삽입되므로 항상 오름차순으로 정렬된 상태를 유지합니다. 따라서 정렬된 두 배열을 병합 과정처럼 두 포인터(two-pointer) 기법으로 순회하면서 최소 거리를 효율적으로 찾을 수 있습니다.
구체적인 알고리즘은 다음과 같습니다.
- 초기화(생성자): 맵 m을 하나 정의하고, 단어 배열을 순회하며 각 단어의 인덱스 i를 m[words[i]]의 끝에 추가합니다.
- shortest(word1, word2) 함수:
- arr1 := m[word1], arr2 := m[word2]로 두 단어의 인덱스 배열을 가져옵니다.
- i := 0, j := 0으로 두고, ret := 무한대(INT_MAX)로 초기화합니다.
- i가 arr1의 크기보다 작고 j가 arr2의 크기보다 작은 동안 다음을 반복합니다.
- ret := min(ret, |arr1[i] − arr2[j]|)
- arr1[i] < arr2[j]이면 i를 1 증가시키고, 그렇지 않으면 j를 1 증가시킵니다.
- ret을 반환합니다.
두 포인터 중 현재 값이 더 작은 쪽만 앞으로 이동시키는 이유는, 더 가까운 쌍이 존재하려면 작은 값 쪽을 키워야 차이가 줄어들기 때문입니다. 이 방식 덕분에 어떤 후보 쌍도 놓치지 않으면서 O(m + n) 시간에 답을 구할 수 있습니다. 여기서 m과 n은 각 단어의 등장 횟수입니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class WordDistance {
public:
unordered_map<string, vector<int>> m;
WordDistance(vector<string>& words) {
for(int i = 0; i < words.size(); i++){
m[words[i]].push_back(i);
}
}
int shortest(string word1, string word2) {
vector<int>& arr1 = m[word1];
vector<int>& arr2 = m[word2];
int i = 0;
int j = 0;
int ret = INT_MAX;
while (i < arr1.size() && j < arr2.size()) {
ret = min(ret, abs(arr1[i] - arr2[j]));
if (arr1[i] < arr2[j]) {
i++;
}
else
j++;
}
return ret;
}
};
main(){
vector<string> v = {"practice", "makes", "perfect", "skill", "makes"};
WordDistance ob(v);
cout << (ob.shortest("skill", "practice")) << endl;
cout << (ob.shortest("makes", "skill"));
}입력
{"practice", "makes", "perfect", "skill", "makes"}
Call shortest("skill", "practice")
Call shortest("makes", "skill")출력
3 1
복잡도 분석
생성자는 단어 목록을 한 번만 순회하므로 O(N) 시간이 걸립니다(N은 전체 단어 수). shortest() 호출은 두 단어의 인덱스 배열 길이의 합에 비례하는 O(m + n) 시간에 처리되며, 호출마다 전체 리스트를 훑는 O(N) 방식보다 반복 조회 상황에서 훨씬 유리합니다. 공간 복잡도는 모든 단어의 인덱스를 저장해야 하므로 O(N)입니다.