[5부 알고리즘] 22장 분할 정복

📌 83) 과반수 엘리먼트 ( 리트코드 169. Majority Element)

✔ 풀이1 (브루트 포스로 과반수 비교) Time Limit Exceeded

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        for num in nums:
            if nums.count(num) > len(nums) // 2:
                return num

✔ 풀이2 (다이나믹 프로그래밍)

from collections import defaultdict
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = defaultdict(int)
        for num in nums:
            if counts[num] == 0:
                counts[num] = nums.count(num)
            
            if counts[num] > len(nums) // 2:
                return num

👉 nums.count(num)은 한번 계산해서 재활용함. 이 풀이는 메모이제이션을 이용한 매우 간단한 다이나믹 프로그래밍 풀이.

✔ 풀이3 (분할 정복)

from collections import defaultdict
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        
        #제일 작은 단위로 쪼개졌을 경우 return (백트래킹)
        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) > half]  #[리스트 l][해당 리스트 인덱스 i] = l[i]

✔ 풀이4 (pythonic way)

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

📌 84) 괄호를 삽입하는 여러 가지 방법 ( 리트코드 241. Different Ways to Add Parentheses)

✔ 풀이 (분할 정복을 이용한 다양한 조합)

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        #계산 함수
        def cal(left, right, op):
            results = []
            for l in left:
                for r in right:
                    results.append(eval(str(l) + op + str(r)))
                
            return results
        
        if expression.isdigit():
            return [int(expression)]
        
        #연산자를 기준으로 분할
        results = []
        for i, char in enumerate(expression):
            if char in '+-*': #char이 연산자 일 경우 분할
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i + 1:])
                
                results.extend(cal(left, right, char))
            
        return results