[LEETCODE 150] - 169 Majority Element

LeetCode의 169번 문제인 "Majority Element" (과반수 원소) 문제입니다

문제에서 주어진것은 정수 배열 nums가 주어지고 배열의 길이는 n입니다.

이 배열에는 반드시 하나의 "과반수 원소"가 존재한다고 가정합니다.

 

수학적 개념으로는 

 

등장횟수 > n /2 이고 

예시 개념으로

배열길이가 7이라면 4번이상 등장하면 과반수

배열길이가 6이라면 4번이상 등장해야 과반수

 

정확히 절반(n/2)는 과반수가 아니게 됩니다.

 

문제에서 요구하는것은 배열 nums 안에서 과반수 원소 하나를 찾아서 반환하라 입니다.

 

이 문제 관련되서는 2가지 방법으로 코드를 풀어봤습니다.(알고리즘 공부)

 

1. 해시맵(딕셔너리)로 빈도수 세는 풀이

Hash Map img

알고리즘 설명

1.각 숫자가 몇 번 나왔는지를 딕셔너리(count)에 누적한다.

2.누적하면서 가장 많이 나온 숫자와 그 빈도를 계속 갱신한다.

3.마지막에 반환값을 준다.

정답 코드(Python)

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = {}
        res, maxCount = 0, 0

        for n in nums:
            count[n] = 1 + count.get(n, 0)
            res = n if count[n] > maxCount else res
            maxCount = max(count[n], maxCount)
        return res

 

Details

1. 숫자별 등장횟수를 저장하는 함수와

res,maxcount = 현재까지 "최다빈도" 숫자와 현재까지 최다 빈도의 값

count = {}
res, maxCount = 0, 0

 

2. n을 하나씩 보면서 빈도 증가

count.get(n, 0)은 n이 처음이면 0부터 시작

for n in nums:
	count[n] = 1 + count.get(n, 0)

 

3.이번에 업데이트된 count[n]이 지금까지의 maxCount보다 크면 → 최다 빈도 숫자를 n으로 바꾸고 아니면 기존 res 유지

res = n if count[n] > maxCount else res

 

4. maxCount 갱신, 최종 최다 빈도 숫자 반환

maxCount = max(count[n], maxCount)

return res

 

이풀이는 과반수라는 조건을 굳이 활용하지 않아도, 최빈값을 찾는 방식이다.

---

2. Boyer-Moore Voting Algorithm 풀이

알고리즘 설명

 

과반수 원소는 전체에서 절반 초과라서, 다른 값들과 1대1 상쇄시켜도 끝까지 남는다는 성질을 이용한다.

후보와 같은 값을 만나면 count +1 다른값을 만나면 count -1이되고

count가 0이 되면 "후보가 약해졌다"는 뜻이니, 다음 값을 새 후보로 설정

 

정답 코드(Python)

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

        for n in nums:
            if count == 0:
                res = n
            count += (1 if n == res else -1)
        return res

 

Details

1. res = 현재 후보 count = 후보의 우세 스코어

res, count = 0, 0

 

2. 배열을 한 번 순회하고 지금 후보가 더 이상 우세하지 않으면 현재값을 새로운 후보로 삼는다

for n in nums:
	if count == 0:
    	res = n

 

3. 현재 값이 후보와 같으면 후보 우세도 증가하고(+1) 다르면 후보 우세도 감소한다(-1). 서로 다른 값이 만나면 상쇄되는 효과

count += (1 if n == res else -1)

 

4. 과반수 원소가 "항상 존재" 한다는 조건에 마지막에 남는 후보가 정답이 된다.

return res

 

과반수 원소는 "나머지 전부"를 합쳐도 더많기때문에 그래서 다른 값과 1대1로 계속 지워나가도, 과반수 원소는 결국 남는다.

---

두 방법 비교 요약

• 딕셔너리 풀이: 빈도 정확히 계산 (직관적, 대신 메모리 사용)
• 투표(Boyer–Moore): 상쇄 논리로 후보만 유지 (메모리 0에 가깝고 깔끔)