Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 알고리즘 풀이: 최단 단어 거리 III(Shortest Word Distance III)

최단 단어 거리 III(Shortest Word Distance III)는 단어 배열에서 두 단어 사이의 최단 거리를 구하는 대표적인 알고리즘 문제입니다. 기본 버전과 달리 이 문제에서는 두 단어가 동일한 문자열일 수 있다는 조건이 추가되어, 같은 단어의 인접한 등장 위치 사이 거리까지 계산해야 하는 점이 핵심 난관입니다.

문제 설명

단어 목록 words와 두 단어 word1, word2가 주어졌을 때, 목록에서 이 두 단어 사이의 최단 거리를 찾아야 합니다. word1과 word2는 서로 같은 단어일 수도 있으며, 이 경우 배열 내 서로 다른 두 개의 개별 위치를 의미합니다.

예를 들어 다음과 같은 단어 배열이 있다고 가정해 보겠습니다.

words = ["practice", "makes", "perfect", "skill", "makes"]

입력이 word1 = "makes", word2 = "skill"일 때, "makes"는 인덱스 1과 4에, "skill"은 인덱스 3에 위치합니다. 가능한 거리는 |3 − 1| = 2와 |4 − 3| = 1이므로 출력 결과는 1이 됩니다.

해결 전략

배열을 한 번만 순회하면서 두 단어의 가장 최근 등장 인덱스를 추적하면 O(n) 시간 복잡도로 문제를 해결할 수 있습니다. 단어가 일치할 때마다 두 위치의 차이를 계산하고, 그중 최솟값을 계속 유지하는 방식입니다.

특히 word1 == word2인 경우가 핵심 포인트입니다. 현재 위치로 l2를 갱신하기 직전에 l1을 이전 l2 값으로 옮겨주면, 같은 단어의 인접한 두 등장 위치 사이 거리를 정확하게 구할 수 있습니다.

단계별 풀이 과정

  1. 변수 초기화 — 결과값 ret := 10⁹, word1의 마지막 위치 l1 := 10⁹, word2의 마지막 위치 l2 := −10⁹으로 초기화합니다.
  2. 배열 크기 저장 — n := words의 크기를 저장합니다.
  3. 순회하며 갱신 — i를 0부터 n 미만까지 증가시키며 다음을 반복합니다.
    • words[i]가 word1과 같다면 l1 := i로 갱신합니다.
    • words[i]가 word2와 같다면 다음을 처리합니다.
      • word1 == word2라면 l1 := l2로 설정하여 이전 등장 위치를 보존합니다.
      • l2 := i로 갱신합니다.
    • ret := min(|l2 − l1|, ret)으로 결과값을 갱신합니다.
  4. 결과 반환 — 모든 순회가 끝나면 ret을 반환합니다.

C++ 구현 예제

아래 예제 코드를 통해 실제 구현 방법을 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int shortestWordDistance(vector<string>& words, string word1, string word2) {
      int ret = 1e9;
      int l1 = 1e9;
      int l2 = -1e9;
      int n = words.size();
      for (int i = 0; i < n; i++) {
         if (words[i] == word1) {
            l1 = i;
         }
         if (words[i] == word2) {
            if (word1 == word2) {
               l1 = l2;
            }
            l2 = i;
         }
         ret = min(abs(l2 - l1), ret);
      }
      return ret;
   }
};
int main(){
   Solution ob;
   vector<string> v = {"practice", "makes", "perfect", "skill", "makes"};
   cout << (ob.shortestWordDistance(v, "makes", "skill"));
}

입력

{"practice", "makes", "perfect", "skill", "makes"}, "makes", "skill"

출력

1

복잡도 분석

시간 복잡도: O(n) — 배열을 한 번만 순회하므로 단어 개수에 비례합니다.
공간 복잡도: O(1) — 몇 개의 변수만 사용하므로 추가 메모리가 필요하지 않습니다.

마무리

이 문제의 핵심은 같은 단어가 두 번 주어질 때 이전 등장 위치를 잃어버리지 않도록 갱신 순서를 조정하는 것입니다. l1을 먼저 이전 l2 값으로 백업한 뒤 l2를 현재 인덱스로 업데이트하는 패턴만 익히면, 기본형 최단 단어 거리 문제와 동일한 구조로 깔끔하게 해결할 수 있습니다.