C++로 구현하는 목표 색상까지의 최단 거리 알고리즘

값이 1, 2, 3 세 가지 색상으로만 이루어진 배열 colors가 있다고 가정해 보겠습니다. 여기에 여러 개의 쿼리(query)가 주어지며, 각 쿼리는 두 개의 정수 i(인덱스)와 c(목표 색상)로 구성됩니다. 우리가 해야 할 일은 인덱스 i와 색상 c 사이의 최단 거리를 찾는 것이고, 만약 해당 색상이 배열에 존재하지 않아 해가 없다면 -1을 반환해야 합니다.

예를 들어 색상 배열이 [1,1,2,1,3,2,2,3,3]이고, 쿼리 배열이 [[1,3],[2,2],[6,1]]이라면 출력은 [3,0,3]이 됩니다.

인덱스 1에서 가장 가까운 색상 3은 인덱스 4에 있으므로 거리는 3입니다.
인덱스 2에서 가장 가까운 색상 2는 자기 자신(인덱스 2)이므로 거리는 0입니다.
인덱스 6에서 가장 가까운 색상 1은 인덱스 3에 있으므로 거리는 3입니다.

문제 해결 접근 방법

이 문제는 각 색상별로 등장하는 인덱스를 미리 저장한 뒤, 이진 탐색(lower_bound)을 활용하면 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

4개의 행을 가진 벡터 index를 생성하고, n을 색상 배열의 원소 개수로 설정합니다.
0부터 n-1까지 반복하면서 각 인덱스 i를 index[colors[i]]에 삽입합니다. 즉, 색상별 등장 위치 목록을 만듭니다.
각 쿼리에 대해 x := queries[i][0], c := queries[i][1]로 설정합니다.
index[c]의 크기가 0이면(해당 색상이 없으면) 결과에 -1을 넣고 다음 쿼리로 건너뜁니다.
lower_bound를 사용해 x보다 크거나 같은 첫 번째 원소의 위치(it)를 찾습니다.
op1과 op2를 무한대(INT_MAX)로 초기화합니다.
it이 index[c]의 끝이면 하나 감소시킨 뒤 op1 := |x − index[c][it]|로 계산합니다.
it이 0이면 op1 := |x − index[c][it]|만 계산합니다.
그 외의 경우에는 op1 := |x − index[c][it]|를 계산한 후 it을 하나 감소시켜 op2 := |x − index[c][it]|도 계산합니다. 즉, 왼쪽과 오른쪽 후보를 모두 확인합니다.
op1과 op2 중 최솟값을 결과 배열 ret에 삽입합니다.

모든 쿼리를 처리한 후 ret을 반환하면 됩니다.

C++ 구현 예제

아래 구현 코드를 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
      vector < vector <int> >idx(4);
      int n = colors.size();
      for(int i = 0; i < n; i++){
         idx[colors[i]].push_back(i);
      }
      vector <int> ret;
      for(int i = 0; i < queries.size(); i++){
         int x = queries[i][0];
         int c = queries[i][1];
         if(idx[c].size() == 0){
            ret.push_back(-1);
            continue;
         }
         int it = lower_bound(idx[c].begin(), idx[c].end() , x) - idx[c].begin();
         int op1 = INT_MAX;
         int op2 = INT_MAX;
         if(it == idx[c].size()){
            it--;
            op1 = abs(x - idx[c][it]);
         }
         else if(it == 0){
            op1 = abs(x - idx[c][it]);
         }
         else{
            op1 = abs(x - idx[c][it]);
            it--;
            op2 = abs(x - idx[c][it]);
         }
         ret.push_back(min(op1, op2));
      }
      return ret;
   }
};
main(){
   vector<int> v = {1,1,2,1,3,2,2,3,3};
   vector<vector<int>> v1 = {{1,3},{2,2},{6,1}};
   Solution ob;
   print_vector(ob.shortestDistanceColor(v, v1));
}

입력

[1,1,2,1,3,2,2,3,3]
[[1,3],[2,2],[6,1]]

출력

[3,0,3]

이 알고리즘의 시간 복잡도는 전처리 단계에서 O(n), 각 쿼리마다 O(log n)이므로 전체적으로 O(n + q·log n)입니다. 여기서 n은 배열의 길이, q는 쿼리의 개수입니다. 덕분에 쿼리가 많은 상황에서도 매우 효율적으로 동작합니다.