문제 조건
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- 0 <= k <= 10^5
nums[i] == nums[j]이고 abs(i - j) <= k를 만족하는 값이 있으면 true 없으면 false를 반환한다.
문제 해결
문제 해결 로직
해당 문제는 해시맵을 사용하여 해결할 수 있다.
배열의 값들을 해시맵에 저장하다가 이미 값이 있으면 i-j를 비교하여 확인한다.
데이터 입력
값과 위치를 저장할 HashMap이 필요합니다..
map
조건 확인
hashmap에 저장된 key값과 배열의 값이 겹치지 않으면 해당 값을 배열에 저장한다. value는 위치로 저장한다.
반복하다가 만약 key 값과 배열의 값이 겹치면 abs(i-j) <= k 조건을 확인한다.
만족하면 true를 반환하고, 아니면 해당 key의 value 값을 업데이트 한다.
배열을 다 돌았다면 true 조건이 없으므로 false를 반환한다.
for(int i=0; i<nums.length; i++){
if(map.get(nums[i]) == null){
map.put(nums[i],i);
}else{
if(Math.abs(i-map.get(nums[i])) <= k){
return true;
}
map.put(nums[i],i);
}
}
return false;코드 작성
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++){
if(map.get(nums[i]) == null){
map.put(nums[i],i);
}else{
if(Math.abs(i-map.get(nums[i])) <= k){
return true;
}
map.put(nums[i],i);
}
}
return false;
}
}복잡도 계산
-
시간 복잡도
- 해당 코드에서 반복문이 배열을 순회하는 만큼 반복하기 때문에 배열의 크기 n만큼 시간복잡도를 가진다.
- 따라서 총 시간 복잡도는 O(n)이 된다.
-
공간 복잡도
- 공간 복잡도는 고유한 배열 요소만큼 가지게 되는데 최악의 경우 배열의 요소가 모두 겹치지 않는 것 이므로 배열의 크기인 n만큼의 공간복잡도를 가진다.
- 따라서 총 공간 복잡도는 O(n)이 된다.
회고
- 다음과 같은 점수를 기록했다.
- 가장 간단한 생각으로 푸는 방법은 단순히 배열을 순회하며 문제에 주어진 조건식으로 확인하여 해당 조건을 만족하는 경우가 나왔을 때 true를 반환하면 된다.
