[1스4코2파] #149. LeetCode 169. Majority Element

gunny·2023년 6월 1일

LeetCode 169 LeetCode 169 python LeetCode Majority Element LeetCode Majority Element python leetcode

코딩테스트

목록 보기

150/530

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (149일차)
[4코1파] 2023.01.13~ (140일차)
[1스4코1파] 2023.04.12~ (51일차)
[1스4코2파] 2023.05.03 ~ (30일차)

Today :

2023.06.01 [149일차]
LeetCode patterns
169. Majority Element
https://leetcode.com/problems/majority-element/description/

1396. Design Underground System

문제 설명

https://leetcode.com/problems/design-underground-system/description/

문제 풀이 방법

collections 모듈의 Counter를 써서
most_common() 활용해버리기..

다른 새럼 코드 보니까 수학을 이용했더라고..
가장 많은 빈도수의 숫자들이 주어진 nums의 리스트의 길이의 절반의 인덱스에 위치하므로 주어진 nums 의 리스트(배열)을 sort 하고, 인덱스로 찾아옴.
눈으로는 봤는데 머리가 이해를 못하네

출처 : https://heestory217.tistory.com/entry/LeetCode-169-Majority-Element

그리고 Boyer-Mooore 과반수 투표 알고리즘이라는 방법으로도 풀 수 있다고 함

내 코드

첫 번째 그냥 생각나는 대로 풀었던 풀이

from collections import Counter

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        return Counter(nums).most_common()[0][0]

다른 새럼의 풀이를 보고 가져온 풀이

from collections import Counter

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

그리고 이번에 정ㅋ복 한 Boyer-moore major vote Algorithm


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

증빙