참고
문제해설
NOTE
•
입력 값 ⇒ 정수배열과, 정수 k 값
•
출력 값 ⇒ 정수 배열에서 k이내의 간격으로 중복되는 값이 있는지 여부
문제 로직고민
NOTE
•
처음으로 생각한 풀이 방법은 슬라이딩 윈도우다.
◦
배열의 요소를 순회하면서, k만큼의 간격이므로 본인을 포함해 2k+1 길이에 해당 요소의 값이 2개이상 있으면 true이다.
◦
단 처음과 끝부분에서는 크기가 잘리므로 따로 연산을 처리해줘야 한다.
◦
Map을 사용해서 각 요소의 개수를 카운팅하고, 만약 해당값이 2개이상이면 true를 반환한다.
•
처음에는 괜찮다고 생각했는데, k의 길이가 배열의 길이와 같을수도 있다.
•
이렇게 된다면 따로 연산을 처리하는 연산이 주가 되버리므로 슬라이딩 윈도우가 쓸모없어진다.
•
Map을 사용해서 해당 값의 위치를 계속해서 갱신해나간다
◦
위의 방식에서 Map을 카운팅 용도로 사용하지말고, 위치를 기록하는 관점으로 바꾸었다.
◦
이렇게 되면, 배열을 순회하면서 나와 동일한 값이 왼쪽방향으로 k안에 있는지 알 수 있다.
작성코드
NOTE
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap();
for(int i =0; i<nums.length; i++){
if(map.containsKey(nums[i]) && i - map.get(nums[i]) <= k ) return true;
map.put(nums[i], i);
}
return false;
}
}
Java
복사
정답코드
NOTE
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> window = new HashSet<>();
int left = 0;
for (int right = 0; right < nums.length; right++) {
if (window.size() > k) {
window.remove(nums[left]);
left++;
}
if (window.contains(nums[right])) {
return true;
}
window.add(nums[right]);
}
return false;
}
}
Java
복사
메모리를 덜 사용하면서 다른풀이
•
처음 생각했던 슬라이딩 윈도우 방식의 풀이가 있었다.
•
if문이 내가 생각했던 초기와 끝의 연산을 따로 처리해주는 부분인것같은데, 생각보다 단순해서 신기했다. 위의 방식은 단순히 한쪽 방향의 k만 생각한 반면, 나는 양쪽의 k를 생각해서 복잡해진거 같다.