문제 개요
배열 하나와 정수 k가 주어졌을 때, 배열 안에서 서로 다른 두 인덱스 i와 j가 존재하여 다음 두 조건을 동시에 만족하는지 판별하는 문제입니다.
- nums[i] = nums[j] (두 위치의 값이 같음)
- |i − j| ≤ k (두 인덱스의 절댓값 차이가 k 이하)
예를 들어 입력 배열이 [1, 2, 4, 1]이고 k = 3이라면, 값 1이 인덱스 0과 3에 존재하고 두 인덱스의 차이가 3으로 k 이하이므로 결과는 True가 됩니다.
해결 접근 방식
이 문제는 값과 인덱스를 묶어 정렬한 뒤 인접한 원소들을 비교하는 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- (값, 인덱스) 형태의 pair를 저장할 배열 nn을 정의합니다.
- 배열 nums를 순회하면서 각 값과 해당 인덱스를 nn에 삽입합니다.
- nn을 오름차순으로 정렬합니다. 정렬 후에는 같은 값들이 서로 인접하게 배치됩니다.
- 정렬된 nn을 순회하며 인접한 두 원소를 비교합니다. 값이 같고 인덱스 차이의 절댓값이 k 이하라면 true를 즉시 반환합니다.
- 모든 원소를 확인했는데도 조건을 만족하는 쌍이 없다면 false를 반환합니다.
C++ 구현 코드
아래 코드를 통해 실제 구현 방법을 더 자세히 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
vector<pair<int, int>> nn;
for (int i = 0; i < nums.size(); i++) {
nn.push_back(make_pair(nums[i], i));
}
sort(nn.begin(), nn.end());
for (int i = 1; i < nn.size(); i++) {
if (nn[i].first == nn[i - 1].first && abs(nn[i].second - nn[i - 1].second) <= k)
return true;
}
return false;
}
};
main(){
Solution ob;
vector<int> v = {1,2,4,1};
cout << (ob.containsNearbyDuplicate(v, 3));
}실행 결과
입력:
{1,2,4,1}출력:
1
출력값 1은 true를 의미하며, 조건을 만족하는 두 인덱스가 실제로 존재함을 나타냅니다.
복잡도 분석
- 시간 복잡도: O(n log n) — 배열 전체를 정렬하는 데 드는 비용이 지배적입니다.
- 공간 복잡도: O(n) — 값과 인덱스를 저장하는 추가 배열이 필요합니다.
참고: 더 효율적인 대안
정렬 기반 접근 대신 해시 맵(unordered_map)을 활용하면 시간 복잡도를 O(n)까지 줄일 수 있습니다. 각 값의 마지막 등장 인덱스만 저장하고, 새로운 위치와의 거리가 k 이하인지 확인하는 방식입니다. 입력 크기가 클 때 유용한 최적화 기법이므로 함께 기억해두면 좋습니다.