LeetCode DSA 시리즈 #7: 169. 다수 원소

Source: Dev.to

문제

이것은 챌린지의 7일 차 시도입니다 (어제 제출을 놓쳤습니다). 오늘 문제는 169. Majority Element 입니다.

크기 n인 배열 nums가 주어지면, 다수 요소를 반환합니다.

다수 요소는 ⌊n / 2⌋보다 많이 나타나는 요소입니다. 배열에 다수 요소가 항상 존재한다고 가정합니다.

해결법

from collections import Counter
from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = Counter(nums)
        majority = len(nums) / 2

        for k, v in counts.items():
            if v > majority:
                return k

복잡도

• Time: O(N) – 리스트를 한 번 순회해 카운터를 만들고, 다시 한 번 순회해 다수 요소를 찾습니다.
• Space: O(N) – 카운터는 최대 N개의 서로 다른 요소를 저장할 수 있습니다.