169, Majority Element

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        std = len(nums) / 2
        _map = {}
        for i in nums:
            try:
                _map[i]
            except KeyError:
                _map[i] = 0
            finally:
                _map[i] += 1
                if _map[i] > std:
                    return i

• 파이썬 스타일 가이드에 따라 가독성, 명확성, 간결성 있게 코드를 작성해보았다.

 

from collections import defaultdict 를 사용하면, 특정 타입에 대한 dict를 초기화할 수 있는데 KeyError를 방지할 수 있다.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        from collections import defaultdict
        
        std = len(nums) / 2
        _map = defaultdict(int)
        for i in nums:
            _map[i] += 1
            if _map[i] > std:
                return i

• 일반적인 코드 같지만, 난 뭔가 위에가 더 좋다.
• 성능은 비슷하다.

 

list에 count() 내장 함수를 사용하면 동일한 값의 개수를 리턴합니다.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        std = len(nums) / 2
        map_ = {}
        for i in nums:
            if not i in map_:
                map_[i] = nums.count(i)
            if map_[i] > std:
                return i

 

파이썬 스타일 가이드에서는 명령형보다는 선언형으로 코드로 작성하는 것을 권장합니다.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        from collections import Counter
        
        std = len(nums) / 2
        map_ = dict(Counter(nums))

        # return [k for k, v in map_.items() if v > std][0]
        return next(filter(lambda x: map_[x] > std, map_))

• Counter 를 사용하면 Counter({3: 2, 2: 1})의 결과를 얻을 수 있는데 dict() 로 감싸면 일반적인 dict 가 된다.
• 명령형 vs. 선언형 차이를 예시로 들면,
  • map_ = {} 초기화 후, loop 를 돌면서 map_ 의 값을 채워주는 것이 명령형.
  • map_ = dict(Counter(nums)) 처럼 map_ 은 {3: 2, 2: 1} 이라고 선언하는 게 선언형.

 

Follow-up: Could you solve the problem in linear time and in O(1) space?

풀이를 보니 Moore's Voting 알고리즘을 사용하면 공간복잡도 O(1)로 문제를 풀 수 있다고 한다.

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

        for num in nums:
            if cnt == 0:
                cur = num
                cnt = 1
            elif cur == num:
                cnt += 1
            else:
                cnt -= 1

        return cur