Daily LeetCode Challenge - 219. Contains Duplicate II

Problem From.
https://leetcode.com/problems/contains-duplicate-ii/

오늘 문제는 주어진 배열에서 중복되는 숫자를 찾는데, 그 중복되는 숫자들의 index 값의 차가 주어진 수 K 보다 작으면 true 를 반환하는 문제였다.

제일 먼저 생각난 풀이법은 이중 for 문을 사용하여, 첫번째 for 문은 배열을 처음부터 탐색하고, 두번째 for 문은 첫번째 for 문 보다 1 큰 index 부터 탐색해나가며, 같은 숫자를 찾는다.
같은 숫자가 찾아졌으면 그 index 를 빼서 그 수가 k 보다 작으면 true 를 반환하게 만드는 것이다.

하지만 위와 같은 방법으로 코드를 짜면 시간복잡도 (time complexity) 가 O(n^2) 가 되어버려서, 너무 낭비가 생기게 된다. 그래서 탐색속도가 빠른 HashMap 을 사용하여 풀이하기로 했다.

배열을 처음부터 탐색하며 map 에 숫자를 key, index 를 value 로 하여 집어넣고, map 안에 key 값이 있는지 확인한 후, 있으면 value 를 가져와 넣으려고 했던 숫자의 index 와 비교하여 k 보다 작으면 true 를 반환하였다.

class Solution {
    fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
        
        val map = HashMap<Int, Int>()
        
        nums.forEachIndexed { index, num ->
            
            if(map.containsKey(num) && index - map.get(num)!! <= k) return true
            
            map.put(num, index)
        }
        
        return false
        
    }
}

위와 같은 방법으로 풀면 시간복잡도가 O(N) 이 되어서 훨씬 효율적인 코드가 된다.
난이도는 easy 인 문제이지만 여러가지 방법을 생각해볼 수 있어 좋은 문제였다.