[LeetCode] 1207. Unique Number of Occurrences 해설 및 풀이 (Python, Java)

LeetCode 1207. Unique Number of Occurrences

https://leetcode.com/problems/unique-number-of-occurrences/?envType=study-plan-v2&envId=leetcode-75

 

---

Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.

Example 1:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

 

Example 2:

Input: arr = [1,2]
Output: false

 

Example 3:

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true
 
Constraints:

1 <= arr.length <= 1000
-1000 <= arr[i] <= 1000

 

---

문제 유형

Array Hash Table

 

풀이 방법 도출

 

주어진 정수 배열 arr에서 각 원소가 등장하는 횟수가 모두 서로 다르면 true를 반환하고, 동일한 등장 횟수가 존재하면 false를 반환하는 문제입니다.

 

Python

1. collections.Counter를 사용하여 각 원소의 등장 횟수를 세어 딕셔너리를 생성합니다.
2. 등장 횟수들만 추출하여 리스트로 만든 뒤, 이를 set으로 변환하여 중복을 제거합니다.
3. 등장 횟수 리스트와 set의 길이를 비교하여 길이가 같으면 true, 다르면 false를 반환합니다.

Java 

1. Map<Integer, Integer>을 이용해 숫자별 등장 횟수 계산합니다.
2. 등장 횟수만 모은 Set<Integer>에 하나씩 추가합니다.
3. 이미 존재하는 횟수가 있다면 false, 아니면 true를 반환합니다.

 

시간 복잡도

• collections.Counter : O(n)
• set : O(n)
• 총 시간 복잡도 : O(n)

---

Python 코드

 

from collections import Counter
from typing import List

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        # 각 숫자의 등장 횟수를 세기
        count_dict = Counter(arr)
        
        # 등장 횟수만 추출하여 리스트로 만들기
        frequency_list = list(count_dict.values())
        
        # 등장 횟수 리스트에서 중복을 제거하여 set과 비교
        # 길이가 같으면 모든 빈도가 유일함
        return len(frequency_list) == len(set(frequency_list))

 

 

Java 코드

 

 

import java.util.*;

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        // Map을 사용하여 숫자별 등장 횟수를 세기
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : arr) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // 등장 횟수만 Set에 넣어서 중복 확인
        Set<Integer> occurrences = new HashSet<>();
        for (int freq : countMap.values()) {
            // 이미 존재하는 경우라면 중복된 횟수 존재하기 때문에 false 반환
            if (!occurrences.add(freq)) {
                return false;
            }
        }