[코테] Majority Element

문제링크

Majority Element - LeetCode

<로직 고민/>

• 배열의 요소를 하나씩 순회하며 .count() 메서드로 비교하는 로직을 처음에 생각했다
• 변수 answer를 0으로 초기화 해서 배열의 각 요소 값의 개수와 배열의 answer 값의 개수를 비교해서 answer 보다 많으면 answer에 넣고 아니면 패스하는 형식이다

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        answer = 0
        for i in range(len(nums)):
            if nums.count(nums[i]) >= nums.count(answer):
                answer = nums[i]
        return answer

• 이렇게 하니까 시간초과가 떴다
• 최대길이의 1 아니면 2로 가득 찬 배열인 경우에 모든 요소를 count() 해서 그런 것 같다
• 이제 count를 한 번 하면 해당 요소를 삭제하는 방식으로 ,,, 하면 안 되겠구나 해당 요소가 전부 삭제되는 게 아니니까
• 그럼 방법을 바꿔서 배열에 set()함수를 이용해서 값을 구해야 하는 요소들을 추출해서 새로운 집합을 만든 다음 그 집합을 for문에 돌려서 nums에 있는 해당 값들을 count 해서 각각 비교해야겠다
• 오 테스트 통과~
• 근데 공간복잡도에서 별로 좋은 점수를 못 받았다
• 새로운 변수를 생성하지 않고 구하는 방법도 있나보군

---

<완성된 풀이/>

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        answer = 0
        nums_set = set(nums)
        for num in nums_set:
            if nums.count(num) >= nums.count(answer):
                answer = num
        return answer

---

<다른 사람 풀이/>

- 정렬을 활용한 방법

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

• 와 이게 뭐지
• 배열의 중간 인덱스에 해당하는 요소가 정답인건가...
• 진짜 어떻게 이런 생각을 하지?
• [1,1,2,2,3,3,4,4,5,5,5]
• 이러면 답이 안 되는 거 아닌가??

• 문제를 잘 읽자222222(휴...)

---

- hashmap을 활용한 방법

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        m = defaultdict(int)
        
        for num in nums:
            m[num] += 1
        
        n = n // 2
        for key, value in m.items():
            if value > n:
                return key
        
        return 0

• 오...코드는 이해가 가는데 hashmap이 뭘까
• 아 hashmap은 해싱(임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑시키는 과정)을 기반으로 하는 자료구조인데, 파이썬에서는 dictionary가 hashmap 자료구조를 따른다
• 딕셔너리를 탐색, 삽입, 삭제
• 문제를 읽고 잘 이해했다면 나는 딕셔너리를 활용했을 것 같다
• 출처1, 2

HashMap | 구보현 블로그

[Python][자료구조] HashMap과 TreeMap, HashSet과 TreeSet

---

- Moore Voting Algorithm

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = 0
        
        for num in nums:
            if count == 0:
                candidate = num
            
            if num == candidate:
                count += 1
            else:
                count -= 1
        
        return candidate

• 이 방법은 어떻게 정답에 이르는 걸까
• 정답 요소가 배열의 과반수를 차지하고 있다면 candidate에 들어갈 확률이 높은 건가
• 이건 확률 문제는 아닌데
• 어떻게 정답이 candidate에 들어가는거지
• 배열이 [6,5,5]일 때, num==6일 때 count가 0이니까 candidate==6이 되고, 다음 if문으로 넘어가서 num==6, candidate==6이니까 count==1, 다음 num==5일 때, num != candidate니까 count는 다시 0, 마지막 num==5일 때 count가 0이니까 candidate에는 5가 들어가고 헐..! 진짜 답이 되네
• 이런 생각은 도대체 어떻게 하는거야..!