(간단한 코드)리트코드 169. Majority Element

 

리스트 안에 가장 많이 있는 숫자를 출력하면 되는 문제이다. 그리고 가장 많이 있는 숫자는 전체의 반 이상을 차지하고 있다.

 

처음에는 이렇게 접근을 했다. 결국은 딕셔너리로 찾으면 되지 않을까?

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        h = defaultdict(int)
        for num in nums:
            h[str(num)] += 1
        
        return int(max(h,key=h.get))

 

여기 나오는 defaultdict(int)은 딕셔너리를 만들 때 if문을 덜 쓰게 도와주는 녀석이다

 

안에 int라고 타입을 지정해줘야 하고, 실제로는 from collections import defaultdict 라고 호출을 해줘야 한다(리트코드에서는 필요 없다)

 

여기서 딕셔너리의 key가 아닌 value를 기준으로 최대를 가져오려면 key = h.get을 사용해야 했는데, 이를 알아두어야지 라는 생각은 안하는게 좋다(어차피 거의 안쓴다), 그냥 이런 방식으로 구할 수 있지 않을까? 정도만 생각하고, 찾아보는게 제일 좋다.

 

이렇게 하면 끝이 나지만, 여기서 기발한 방법을 봤다. 

 

문제에서 "가장 많이 있는 숫자는 전체의 반 이상을 차지하고 있다"라는 문구가 있다.

-> The majority elements is the element that appears more than [n/2] times

 

그 뜻은 해당 숫자 리스트를 순서대로 정렬한 후, "가운데 있는 숫자는 무조건 과반수를 차지하는 숫자"라는 것을 의미한다.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2] #nums리스트에 중앙값을 출력

 

이런 코드도 된다는 것이다. 

 

와 기발하구나... 라는 생각이 들었다.