[LeetCode] - 961. N-Repeated Element in Size 2N Array

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

--> https://leetcode.com/problems/n-repeated-element-in-size-2n-array/description/

 

문제 : 

You are given an integer array nums with the following properties :

nums.length == 2 * n.

nums contains n + 1 unique elements.

Exactly one element of nums is repeated n times.

 

Return the element that is repeated n times.

---

Example 1 :

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

Output : 3

 

Example 2 :

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

Output : 2

 

Example 3 :

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

Output : 5

 

Constraints :

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 10^4
• nums contains n + 1 unique elements and one of them is repeated exactly n times.

---

주어진 정수 배열 nums는 다음과 같은 특징을 가집니다 :

• 배열의 길이는 2 * n입니다.
• nums는 n + 1개의 고유한 요소를 포함하고 있습니다.
• 이 중 한 요소는 정확히 n번 반복됩니다.

이 조건을 만족하는 요소를 반환하는 문제입니다.

 

class Solution {
    public int repeatedNTimes(int[] nums) {
        Map<Integer, Integer> countM = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            countM.put(nums[i], countM.getOrDefault(nums[i], 0) + 1);
        }

        for (Map.Entry<Integer, Integer> entry : countM.entrySet()) {
            if (entry.getValue() == nums.length / 2) { // n times means nums.length / 2
                return entry.getKey();
            }
        }
        return -1;
    }
}

 

이 코드는 주어진 배열 nums에서 정확히 n번 반복되는 요소를 찾는 문제를 해결합니다. 이 문제를 해결하기 위해 HashMap을 사용하여 각 요소의 빈도를 계산한 다음, 그 빈도가 n인 요소를 찾아 반환합니다. 제가 요소의 빈도 찾는 문제가 나오면 늘 생각해 내는 버릇 같은 코드입니다만, 늘 결과를 보면 아쉬운 그런 구현방식입니다. 그래서 나중에 이 코드보다 더 나은 코드를 생각했어야 했습니다. 그래도 설명드리겠습니다 : 

1. 해시맵 초기화 :
   • 각 숫자의 빈도를 저장하기 위해 HashMap을 사용합니다. 키는 배열의 요소이고, 값은 그 요소의 빈도입니다.
2. 요소의 빈도 계산 :
   • 배열 nums를 순회하면서 각 요소의 빈도를 countM 맵에 기록합니다.
   • countM.getOrDefault(nums[i], 0)를 사용하여 해당 요소의 현재 빈도를 가져오고, 없을 경우 기본값 0을 사용합니다.
   • 요소의 빈도를 1 증가시킨 후 맵에 다시 저장합니다.
3. 빈도가 n인 요소 찾기 :
   • 맵의 각 엔트리를 순회하여 빈도가 nums.length / 2인 요소를 찾습니다.
   • 문제의 조건상, 배열의 길이는 2 * n이므로, 정확히 n번 반복되는 요소의 빈도는 nums.length / 2가 됩니다.
4. 결과 반환 :
   • 문제의 제약 조건에 의해 n번 반복되는 요소가 항상 존재하므로 이 부분은 실제로 실행되지 않습니다.

시간 복잡도

• O(n) : 배열을 한 번 순회하여 각 요소의 빈도를 계산하고, 또 한 번 순회하여 빈도가 n인 요소를 찾습니다. 따라서 시간 복잡도는 O(n)입니다.

공간 복잡도

• O(n) : HashMap에 최대 n + 1개의 고유 요소와 그 빈도를 저장하므로, 공간 복잡도는 O(n)입니다.

---

해시맵을 쓴거 까지는 좋은 시도였으나, 굳이 Map.Entry를 써야 한 부분이 걸림돌이 된 거 같습니다. 지금 맑은 정신에 다시 이 문제를 접해보니 훨씬 쉬운 방법이 있었습니다. 바로 HashSet를 쓰는 것입니다 : 

class Solution {
    public int repeatedNTimes(int[] nums) {
        HashSet<Integer> seen = new HashSet<>();
        
        for (int num : nums) {
            if (seen.contains(num)) {
                return num;
            }
            seen.add(num);
        }
        
        return -1; // 이 부분은 절대로 실행되지 않을 것임 (문제 조건상 반드시 반복되는 요소가 존재함)
    }
}

 

제가 너무 문제를 꼬아서 스스로 어렵게 생각해냈나 봅니다. 이렇게 하면 됩니다. 

그래도 여전히 시간 복잡도와 공간 복잡도는 둘 다 O(n) 인 코드입니다.

 

---

내 코드들 Runtime 결과