리트코드 - 219. Contains Duplicate II

리트코드 - 219. Contains Duplicate II

출처 - https://leetcode.com/problems/contains-duplicate-ii/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 정수 배열 nums와 정수 k가 있을 때, 만약 배열 내에 두 개의 서로 다른 인덱스 i와 j가 존재하며, 이때 nums[i]와 nums[j]의 값이 같고 두 인덱스 간의 차이인 abs(i - j)가 k 이하라면, true를 반환합니다.

 

의사코드

map 생성 반복문 시작 [nums 배열 순회, i는 +1씩]     if map이 nums[i]인 key로 가지고 이때 i - value값 <= k이면         true 리턴     map에 key=nums[i]에 인덱스 i 넣음 반복문 종료 false 리턴

 

풀이코드

import java.util.Map;
import java.util.HashMap;

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.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                return true;
            }
            map.put(nums[i],i);
        }   
        return false;
    }
}

코드설명

map을 이용하여 간단하게 구현하였다.

nums배열을 순차적으로 돌며 map에 key는 nums배열 값, value는 인덱스를 넣는다.

만약 이 인덱스가 기존에 map에 저장되어있고, 인덱스의 차가 k이하이면 true를 리턴한다.

 

시간복잡도 - O(n)

공간복잡도 - O(min(n, k))

 

문제를 풀며 생각한 흐름과 배운 점

어렵지 않은 문제였다.

풀고나서 다른 사람 코드를 보는 중에 제목에 슬라이드 윈도우 기법을 쓴 사람이 있길래 따로 코드를 보지 않고 직접 구현해봤다.

 

슬라이드 윈도우

import java.util.Set;

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k == 0) {
            return false;
        }
        
        Set<Integer> slideWindow = new HashSet<>();
  
        for (int i = 0; i < nums.length; i++) {
            if (slideWindow.contains(nums[i])){ 
                return true;
            } 
            if (i >= k) {
                slideWindow.remove(nums[i - k]);
            }
            slideWindow.add(nums[i]);
        }

        return false;
    }
}

처음에는 일반 배열을 이용해서 slideWindow를 만들었는데 0부터 k까지 범위 안에도 만족하는 수가 있을 것 같아서 set을 이용해서 로직을 만들었다.

set에서 값을 넣고 또 포함되어있는지 확인하므로 중복된 내용인 것 같아 for문안에서 전부 처리할 방법을 떠올려 위 코드를 만들었다.

 

이렇게만 생각하고 제출했는데 k가 0일때 테스트케이스를 통과하지 못하여 맨위에 k가 0일때를 추가했다.

 

정리

map과 set의 적절한 사용으로 배열 내 로직을 처리할 수 있다.