📑 문제
- nums[i]는 nums[j]와 같다.
- 인덱스 i와 j 사이의 절대값 거리(abs(i - j))가 k 이하다.
만약 위의 두 조건을 만족하는 두 개의 고유한 인덱스가 배열 내에 있다면 true를 반환하고, 그렇지 않다면 false를 반환하세요
📑 문제 접근 방식
이 문제도 Ransom Note 문제의 풀이 방법과 비슷하게 풀어 해결했습니다.
인덱스 간의 거리를 구해야 했기에, index 맵과 중복된 숫자가 등장한 횟수를 담는 countMap을 생성해 , 해당 숫자가 이미 한번이상 등장했고, 해당 숫자가 등장한 인덱스들간의 차이가 k라면 true로 반환하도록 구현했습니다.
📑 CODE
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer,Integer> countMap = new HashMap<>();
HashMap<Integer,Integer> indexMap = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int num = nums[i];
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
// 해당 숫자가 이미 한 번 이상 등장했고 그 차이가 k 이하라면 true 반환
if(countMap.get(num) > 1 && Math.abs(i - indexMap.get(num)) <= k){
return true;
}
indexMap.put(num,i);
}
return false;
}
}
다른 접근 방식
다른 접근 방식으로는 슬라이딩 윈도우와 HashSet을 이용해 해결한 방법도 있었습니다. 윈도우 크기만큼 요소들 사이에서 중복값 찾아내며, 윈도우의 범위 밖의 요소들은 제거하는 방식입니다.
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < nums.length; i++){
if(i > k) set.remove(nums[i-k-1]);
if(!set.add(nums[i])) return true;
}
return false;
}HashSet과 슬라이딩 윈도우 알고리즘을 사용하는 방법은 생각하지 못했었기 때문에, 다양한 시각으로 문제를 접근하도록 노력해야겠다는 생각이 들었습니다.
