코딩 테스트/파이썬 알고리즘 인터뷰
파이썬 알고리즘 인터뷰 83. 과반수 엘리먼트
스마트코더91
2024. 3. 14. 13:25
https://leetcode.com/problems/majority-element/description/
전체 코드
처음 시도
class Solution:
def __init__(self):
self.is_found = False
self.found_num = -1
def majorityElement(self, nums: List[int]) -> int:
counter = collections.defaultdict(int)
def divide(left, right):
if self.is_found:
return
if left >= right:
counter[nums[left]] += 1
if counter[nums[left]] > (len(nums) // 2):
self.found_num = nums[left]
self.is_found = True
return
mid = (right + left) // 2
divide(left, mid)
divide(mid + 1, right)
divide(0, len(nums) - 1)
return self.found_num
leaf까지 분할한 후 leaf에서 해당 숫자의 개수를 딕셔너리에 저장한다. 개수가 과반이 넘으면 해당 값을 저장하고 계속 백트래킹한다.
동작은 하지만 우아하지 않다.
해설 코드 - 분할 정복 방법
class Solution:
def majorityElement(self, nums: List[int]) -> int:
if nums is None:
return 0
if len(nums) == 1:
return nums[0]
half = len(nums) // 2
a = self.majorityElement(nums[:half])
b = self.majorityElement(nums[half:])
return [b, a][nums.count(a) > len(nums) // 2]
리스트 슬라이싱을 통해 좌우로 분할한다.
len(nums)=2 일 때 [b, a][nums.count(a) > len(nums) // 2] 코드에 의해 백트래킹은 다음과 같이 항상 오른쪽으로 진행된다.
여기서 좌측은 과반수가 넘는 '1'을 선택하지 않았으나 오른쪽은 '1'이 선택되었다. 이는 입력 조건에 '과반수가 넘는' 숫자가 1개 이상 존재하기에 가능하다.
만약 다음과 같이 [1,2,1,3,1,4,1,5]인 경우에는 1이 과반수를 넘지 않기 때문에 해당 함수는 실패할 것이다.
다이나믹 프로그래밍
class Solution:
def majorityElement(self, nums: List[int]) -> int:
counts = collections.defaultdict(int)
for num in nums:
if counts[num] == 0:
counts[num] = nums.count(num)
if counts[num] > len(nums) // 2:
return num
return -1
루프를 순회하면서 각 숫자의 개수를 추가한 후 과반수를 넘으면 바로 반환한다. 속도도 빠르게 동작한다.
파이써닉한 방법
class Solution:
def majorityElement(self, nums: List[int]) -> int:
return sorted(nums)[len(nums) // 2]
특정 숫자가 과반수가 넘기 때문에 정렬된 숫자의 중앙은 반드시 해당 숫자값이다. 따라서 해당 값을 반환한다.