C++로 해결하는 거의 중복 포함 III(Contains Duplicate III) 문제

문제 소개

정수 배열이 주어졌을 때, 배열 안에 서로 다른 두 인덱스 i와 j가 존재하는지 확인하는 문제입니다. 이때 만족해야 할 조건은 다음과 같습니다.

• nums[i]와 nums[j]의 절댓값 차이는 t 이하여야 합니다.
• 인덱스 i와 j의 절댓값 차이는 k 이하여야 합니다.

예를 들어 입력 배열이 [1,2,3,1]이고 k = 3, t = 0이라면, 조건을 만족하는 두 수가 존재하므로 결과는 true(1)가 됩니다.

해결 접근 방식

이 문제는 슬라이딩 윈도우(sliding window) 기법과 multiset을 함께 활용하면 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

1. 정수를 담을 집합 s를 생성하고, n을 nums 배열의 크기로 설정합니다.
2. i를 0부터 n-1까지 순회하며 아래 작업을 반복합니다.
   • x를 nums[i]보다 크거나 같은 값 중 가장 작은 원소(lower bound)의 위치로 지정합니다.
   • x가 집합 범위 안에 있고 그 값이 nums[i] + t 이하라면 true를 반환합니다.
   • x가 첫 번째 원소가 아니라면, 바로 앞의 원소를 확인한 뒤 그 값에 t를 더한 결과가 nums[i] 이상인지 검사하고, 만족하면 true를 반환합니다.
   • nums[i]를 s에 삽입한 후, 윈도우 크기 k를 유지하기 위해 nums[i - k]를 s에서 제거합니다.
3. 모든 원소를 확인한 후에도 조건을 만족하는 쌍이 없다면 false를 반환합니다.

lower_bound 탐색과 삽입·삭제가 모두 O(log n)에 처리되므로, 전체 시간 복잡도는 O(n log n)입니다.

C++ 구현 예시

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        multiset<int> s;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            multiset<int>::iterator x = s.lower_bound(nums[i]);
            if(x != s.end() && *x <= nums[i] + t) return true;
            if(x != s.begin()){
                x = std::next(x, -1);
                if(*x + t >= nums[i]) return true;
            }
            s.insert(nums[i]);
            if(i >= k){
                s.erase(nums[i - k]);
            }
        }
        return false;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,1};
    cout << (ob.containsNearbyAlmostDuplicate(v, 3, 0));
}

입력

[1,2,3,1]
3
0

출력

1

결과가 1(true)로 출력됩니다. 배열 [1,2,3,1]에서 인덱스 0과 3의 값이 모두 1로 동일하여 절댓값 차이가 0(t = 0 이하)이고, 인덱스 차이 역시 3(k = 3 이하)이기 때문입니다.