[Leet Code풀이] 169. Majority Element

문제 설명

https://leetcode.com/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150

리스트에서 과반수를 차지하는 원소를 찾아내는 문제

풀이

접근 방법. Two pointer

1) 전체 원소를 돌면서 딕셔너리를 만듦 2) 만들어진 dict에서 n/2이상인 값 리턴

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = {}
        for i in nums:
            if i not in dic:
                dic[i] = 1
            dic[i] += 1
        
        leng = len(nums)
        for i, v in dic.items():
            if v > leng//2 + 1:
                return i

위 풀이의 시간 복잡도와 공간복잡돈는 아래와 같다.

• 시간 복잡도 : O(N) nums만큼 루프를 도므로 O(N)

• 공간 복잡도 : O(N) dict만큼 추가적인 공간을 사용하므로 O(N) 소요