파이썬으로 배열 요소의 고유한 발생 횟수 확인하기

문제 소개

배열이 하나 주어졌을 때, 배열 안의 각 요소가 서로 다른 등장 횟수(고유한 발생 횟수)를 가지는지 확인하는 문제입니다. 만약 두 개 이상의 요소가 같은 횟수만큼 등장한다면 false를 반환하고, 모든 요소의 등장 횟수가 서로 다르다면 true를 반환해야 합니다.

예를 들어 배열이 [1, 1, 2, 2, 2, 3, 4, 4, 4, 4]라고 가정해 보겠습니다. 이 경우 요소 1은 두 번, 요소 2는 세 번, 요소 3은 한 번, 요소 4는 네 번 등장합니다. 즉, 등장 횟수가 각각 2, 3, 1, 4로 모두 고유하므로 결과는 true가 됩니다.

해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

• 먼저 배열 내 각 요소의 빈도수(frequency)를 계산합니다.
• 빈도 맵(frequency map)의 각 키-값 쌍을 순회하면서 다음을 수행합니다.
  • 해당 값(등장 횟수)이 이미 다른 맵 mp에 존재하면 false를 반환합니다.
  • 존재하지 않는다면 mp[value] = 1로 저장합니다.
• 모든 검사를 통과하면 true를 반환합니다.

핵심 아이디어는 간단합니다. 첫 번째 맵으로 각 요소가 몇 번 나타나는지 구하고, 두 번째 맵으로 그 등장 횟수들 사이에 중복이 있는지 확인하는 것입니다.

예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다.

class Solution(object):
    def uniqueOccurrences(self, arr):
        d = {}
        for i in arr:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
        l = {}
        for x, y in d.items():
            if y in l:
                return False
            l[y] = 1
        return True

ob1 = Solution()
print(ob1.uniqueOccurrences([1,1,2,2,2,3,4,4,4,4]))

입력

[1,1,2,2,2,3,4,4,4,4]

출력

true

복잡도 분석

이 알고리즘의 시간 복잡도는 배열을 한 번 순회하여 빈도수를 계산하고(O(n)), 빈도 맵을 다시 순회하며 중복을 확인하기 때문에 전체적으로 O(n)입니다. 공간 복잡도 역시 두 개의 딕셔너리를 사용하므로 최악의 경우 O(n)입니다.

참고: collections.Counter 활용

파이썬에서는 collections.Counter를 사용하면 코드를 더욱 간결하게 작성할 수 있습니다.

from collections import Counter

class Solution(object):
    def uniqueOccurrences(self, arr):
        counts = Counter(arr).values()
        return len(counts) == len(set(counts))

Counter로 각 요소의 등장 횟수를 구한 뒤, 등장 횟수 목록의 길이와 집합(set)으로 변환한 길이를 비교하면 중복 여부를 한 줄로 판별할 수 있습니다.