[JAVA][LeetCode] #217. Contains Duplicate | easy | HashMap | HashSet | Insertion sort

문제 / 예시 / 제한조건

 

겹치는 항목이 있는지 체크하는 방법

 

HashMap 을 이용

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Boolean> map = new HashMap<>();
        
        for(int num : nums) {
            if(map.containsKey(num)) return true;
            else map.put(num, true);
        }
        
        return false;
    }
}

 

이렇게 풀었당

Time Complexity : O(n)
Space Complexity : O(n)

 

근데 HashMap을 이용하는 것은 Key만 사용하고 내용은 따로 사용하지 않기 때문에

HashSet을 이용하는 것이 좋은 것 같아서, HashSet으로 변경

---

HashSet 을 이용

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> hash = new HashSet<>();

        for(int num : nums) {
            if(hash.contains(num)) return true;
            hash.add(num);
        }

        return false;
    }
}

Time Complexity : O(n)
Space Complexity : O(n)

 

결과가 맘에 들지 않아서 1ms 나온 솔루션을 찾아보았다.

 

찾고 이해하고 다시 풀어보았다!

 

---

class Solution {
    public boolean containsDuplicate(int[] nums) {
        int length = nums.length;

        if(length == 1) return false;
        
        for(int i=1; i<length; i++) {
            int currentValue = nums[i];
            int j=i-1, beforeValue = nums[j];
            boolean changed = false;
            
            // insertion sort
            while(beforeValue > currentValue) {
                changed = true;
                nums[j+1] = beforeValue;

                if(j-- == 0) break;

                beforeValue = nums[j];
            }

            // set current value position.
            if(changed) nums[j+1] = currentValue; 

            // check duplicate
            if(currentValue == beforeValue) return true;
        }
        return false;
    }
}

이 방법은  sort를 하면서 찾아주는 작업이다.

이 방법이 더 오래걸리는 것 처럼 보이는데, 더 빠르다니 신기하다.

 

실제로 시간 복잡도는

Time Complexity : O(n^2)
Space Complexity : O(1)

이렇게 더 느린 것을 볼 수 있는데, 더 빠른 이유는 무엇일까 ?

 

챗지피티한테 물어보니

The last implementation uses an insertion sort algorithm to simultaneously sort the array and check for duplicates. While insertion sort is not generally the most efficient sorting algorithm, in this specific case, it has the potential to be faster for certain inputs due to the early termination when a duplicate is found.

If the input array is already nearly sorted or has only a few duplicates, the insertion sort algorithm might perform fewer operations compared to the first implementation using a HashMap. In such cases, the first implementation may terminate early upon finding a duplicate, resulting in faster execution.

However, the performance of the last implementation heavily depends on the characteristics of the input array. In the worst-case scenario, where the input array is large and contains many duplicates, the insertion sort algorithm's quadratic time complexity may make it slower compared to the linear-time complexity of the HashMap approach.

In general, the efficiency of an algorithm depends on various factors such as the size of the input, the distribution of values in the input, and the specific implementation details. It's essential to consider these factors when evaluating the performance of different algorithms.

라고 한다.

 

내 생각으로는 일반적으로 HashSet을 사용하는 방식이 빠른데, leetcode에 있는 데이터 셋에는 위 방법이 빠른 것으로 나오는 것 같다!

어쨌든 빠른 방법으로 풀어보는 것 까지 성공!