LeetCode Top Interview 150) Majority Element

Question

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Constraints:

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

class Solution:
    def majorityElement(self, nums: List[int]) -> int:

---

---

한 리스트 nums내에서 가장 많이 등장한 수를 반환하는 문제입니다.

제가 생각한 코드는 다음과 같습니다.

from collections import defaultdict

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        d = defaultdict(int)
        max_cnt, answer = 0,0
        for n in nums:
            d[n] +=1
            if max_cnt < d[n]:
                max_cnt = d[n]
                answer = n
        return answer

• d : deafaultdict(int) 딕셔너리로 새로운 키가 추가될 때 값이 0으로 초기화되는 딕셔너리입니다.
• max_cnt : 특정 지점까지 가장 많이 등장한 값의 등장 횟수입니다.
• answer : 가장 많이 등장한 값입니다.
• nums를 처음부터 순회하면서 딕셔너리에 등장할 때 마다 값을 1씩 증가시킵니다.
• max_cnt보다 현재 숫자의 등장횟수인 d[n]이 크다면 max_cnt값을 교체하고 answer도 n으로 저장합니다.
• 전부 순회했다면 answer에는 가장 많이 등장한 값이 저장되어 있을 것이므로 곧바로 answer을 반환합니다.

이번 문제에선 한 번의 순회로 끝내는 것을 목적으로 코드를 작성했습니다. 그런데 통과를 하고 나니 속도는 잘 나왔지만 메모리 사용률이 높게 나왔습니다.

그래서 조건을 살피니 가장 많이 등장하는 값이 리스트 길이의 절반보다 많다는 말이 있었습니다. 왜 굳이 이런 조건을 주었을까 생각하다가(한참...) 얻어걸리면서 답을 찾았습니다.

'정렬을 한다해도 최빈값이 최솟값도 최댓값도 아닌데..' 하다가

'...중앙값은 맞겠는데?'

라는 생각이 들어 코드를 작성하여 제출하니 잘 나왔습니다.

from collections import defaultdict

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

전체 정렬을 하기 때문에 1회차 탐색만 하는 첫 번째가 속도는 더 빠르다