[LeetCode] - 217. Contains Duplicate

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Contains Duplicate" 문제입니다.

--> https://leetcode.com/problems/contains-duplicate/description/

 

문제 :

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

---

Example 1 :

Input : nums = [1,2,3,1]

Output : true

 

Example 2 :

Input : nums = [1,2,3,4]

Output : false

 

Example 3 :

Input : nums = [1,1,1,3,3,4,3,2,4,2]

Output : true

 

Constraints :

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9  

---

이 문제는 주어진 정수 배열에서 중복되는 값이 있으면 true를 반환하고, 모든 요소가 고유하면 false를 반환합니다. 제목 그대로인 문제인데 여러 방식이 있습니다 (푸는 방법이).

제 코드는 해쉬맵을 이용했는데 생각보다 비효율적인 결과가 나와서 다른 유저들의 답안도 들고 와봤습니다.

 

1. 재이의 코드 : 

 

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int num : nums) {
            if (m.containsKey(num) && m.get(num) >= 1) {
                return true;
            }
            m.put(num, m.getOrDefault(num, 0) + 1);
        }
        return false; 
    }
}

 

1. HashMap m은 배열의 각 요소와 그 빈도를 저장합니다.
2. 배열 순회 및 중복 검사:
   • for (int num : nums): 배열 nums의 모든 요소를 순회합니다.
   • if (m.containsKey(num) && m.get(num) >= 1): 현재 요소 num이 이미 HashMap에 존재하고, 빈도가 1 이상이면 중복되는 값이 있다는 의미이므로 true를 반환합니다.
   • m.put(num, m.getOrDefault(num, 0) + 1): 현재 요소 num을 HashMap에 추가하거나, 이미 존재하는 경우 빈도를 1 증가시킵니다.
3. 모든 요소가 고유한 경우 : 배열을 모두 순회한 후에도 중복되는 요소가 없으면 false를 반환합니다.

요약하자면 이 코드는 HashMap을 사용하여 배열의 요소 빈도를 추적하고, 중복 요소를 확인합니다. 중복 요소가 발견되면 즉시 true를 반환하고, 그렇지 않으면 배열을 끝까지 확인한 후 false를 반환합니다. O(n)의 시간 복잡도를 가집니다.

---

2. Hash Set를 이용한 답안 : 

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num))
                return true;
            seen.add(num);
        }
        return false;
    }
}
// rahulvarma5297 유저의 코드

 

 

이 코드는 Hash Set을 이용한 코드입니다. 아이디어는 HashMap 쓴 코드랑 비슷하지만, HashSet은 알아서 중복된 것을 추가하지 않는 성질이 있기 때문에 보다 더 효율적입니다. 시간 복잡도는 O(n) 입니다.

---

3. Sort를 한 답안 : 

 

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums); 
        for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] == nums[i+1]) {
                    return true;
                }
        }
        return false;
    }
}
// Primordial_Black 유저의 코드

 

이 코드는 제 코드나, Hash Set을 쓴 코드 보다 시간 복잡도면에서는 느리지만 (O(nlogn)), 공간적인 면에서는 효율적이라서 넣어봤습니다.

---

1,2,3 코드들의 Runtime 결과