LeetCode-169 Majority Element 파이썬 풀이

Majority Element - LeetCode

문제

int 형 배열 안에서 가장 많이 존재하는 값을 반환하는 문제 입니다. 

풀이

nums를 순회하며 각 요소들의 숫자를 세는 방식입니다. a라는 배열에 nums안의 요소들을 중복없이 저장하고 count라는 배열에 a의 각 요소들이 nums안에서 몇 개나 존재하는지를 저장합니다.

예를들어 nums = [1,1,2,2,2,3] 이라면 a = [1, 2, 3]이되고 count = [ 2, 3, 1 ] 입니다. 이런 방식으로 저장하기 위해서는 nums의 요소들을 하나씩 꺼내어 해당 요소가 a안에 없다면 a에 append하여 저장하고 count 배열에 1을 저장합니다. a와 count의 인덱스가 동일하기 때문에 어떤 요소가 몇개 존재하는지 인덱스를 통해 쉽게 판별할 수 있습니다. 만약 순회하다 a안에 존재하는 요소를 마주쳤을땐 a안의 존재하는 해당 요소의 인덱스를 조회한 후 count 배열의 동일한 인덱스의 요소를 +1하여 저장합니다. nums순회를 마친 후에는 count 배열 중 가장 큰 값의 인덱스를 조회하여 a 배열의 동일한 인덱스를 가진 요소를 반환하면 됩니다.

이 방법은 nums를 한번만 순회하기때문에 o(n)을 시간 복잡도로 가집니다.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        a = []
        count = []
        for i in range(0,len(nums)):
            if nums[i] not in a:
                a.append(nums[i])
                count.append(1)
            else:
                count[a.index(nums[i])] = count[a.index(nums[i])]+1
        return a[count.index(max(count))]