C++로 배열에서 k 거리 이내에 중복 요소가 있는지 확인하는 방법

문제 개요

정렬되지 않은 배열에서 서로 k 거리 이내에 중복된 요소가 존재하는지 확인하는 방법을 알아보겠습니다. 예를 들어 요소 목록이 {1, 2, 3, 1, 4, 5}이고 k = 3이라면, 두 개의 1 사이 거리가 3이므로 프로그램은 true를 반환합니다.

이 문제는 해시 테이블(std::set)을 활용한 슬라이딩 윈도우 기법으로 효율적으로 해결할 수 있습니다. 항상 현재 위치에서 k 거리 이내의 요소들만 집합에 유지하기 때문에 전체 시간 복잡도는 O(n)입니다.

알고리즘 접근 방식

• 빈 해시 테이블(집합)을 하나 생성합니다.
• 각 인덱스 i에 대해 요소 e = arr[i]를 순서대로 처리합니다.
  • e가 이미 해시 테이블에 존재하면 true를 즉시 반환합니다.
  • 그렇지 않으면 e를 해시 테이블에 추가하고, i >= k일 때 (i-k)번째 요소가 집합에 있다면 제거합니다.

이 과정을 통해 집합에는 항상 최근 k개의 요소만 남게 되며, 새로운 요소가 이 범위 안의 어떤 요소와도 일치하지 않는다는 것을 빠르게 판별할 수 있습니다.

C++ 구현 예제

#include<iostream>
#include<set>
using namespace std;

bool hasDuplicateWithDistK(int arr[], int n, int k) {
    set<int> element_set;
    for (int i = 0; i < n; i++) {
        // 현재 요소가 이미 k 거리 이내에 존재하는지 확인
        if (element_set.find(arr[i]) != element_set.end())
            return true;
        element_set.insert(arr[i]);
        // 윈도우 크기 유지: k 거리를 벗어난 요소 제거
        if (i >= k)
            element_set.erase(arr[i - k]);
    }
    return false;
}

int main() {
    int arr[] = {10, 5, 3, 4, 3, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    if (hasDuplicateWithDistK(arr, n, 3))
        cout << "중복 요소가 발견되었습니다";
    else
        cout << "중복 요소가 발견되지 않았습니다";
    return 0;
}

출력 결과

중복 요소가 발견되었습니다

동작 원리 분석

위 예제에서 배열은 {10, 5, 3, 4, 3, 5, 6}이고 k = 3입니다. 값 3은 인덱스 2와 인덱스 4에 위치하며 두 거리가 2로 k 이내이므로 중복으로 판단됩니다.

반면 k = 1인 경우에는 인접한 두 요소만 비교 대상이 되므로 같은 배열에서도 false가 반환됩니다. 이처럼 k 값에 따라 결과가 달라질 수 있습니다.

복잡도 분석

• 시간 복잡도: O(n log k) — 각 요소마다 크기가 최대 k인 std::set에서 탐색·삽입·삭제가 이루어집니다. unordered_set을 사용하면 평균 O(n)까지 개선할 수 있습니다.
• 공간 복잡도: O(k) — 집합에는 항상 최대 k개의 요소만 저장됩니다.