분할 정복

Question 83: 과반수 엘리먼트

과반수를 차지하는 엘리먼트를 출력하라.

입력: nums = [3,2,3]

출력: 3

---

내 풀이

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums_count = collections.Counter(nums)
        return nums_count.most_common(1)[0][0]

• 약간의 꼼수를 사용했다.

결과

Runtime: 188 ms, faster than 68.08% of Python3 online submissions for Majority Element. Memory Usage: 15.5 MB, less than 87.29% of Python3 online submissions for Majority Element.

풀이 1: 브루트 포스로 과반수 비교

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

중요 내용

1. nums 안의 모든 수를 반복문으로 돌면서 과반수를 차지하는지 체크한다.
2. 시간 초과 에러가 뜬다.

풀이 2: 다이나믹 프로그래밍

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

중요 내용

1. 풀이 1와 결과가 나오는 과정은 같으나 연산 횟수를 줄여서 최적화를 하였다.

풀이 3: 분할 정복

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if not nums:
            return None
        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]

중요 내용

1. 분할된 리스트에서 과반수를 차지하는 수를 리턴하는 재귀함수로 접근하였다.

풀이 4: 파이썬다운 방식

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

중요 내용

1. 정렬한 후에 가운데를 지정하면 반드시 과반수 이상의 수이다.

---

Question 84: 괄호를 삽입하는 여러 가지 방법(재풀이)

숫자와 연산자를 입력받아 가능한 모든 조합의 결과를 출력하라.

입력: ‘2-1-1’

출력: [0, 2]

설명: ((2-1)-1) = 0 (2-(1-1)) = 2

---

풀이 1: 분할 정복을 이용한 다양한 조합

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        def compute(left, right, op):
            compute_result = []
            for l in left:
                for r in right:
                    compute_result.append(eval(str(l)+op+str(r)))
            return compute_result
        
        if expression.isdigit():
            return [int(expression)]
        
        results = []
        for index, value in enumerate(expression):
            if value in '*-+':
                left = self.diffWaysToCompute(expression[:index])
                right = self.diffWaysToCompute(expression[index+1:])
                results.extend(compute(left, right, value))

        return results

중요 내용

1. 재귀함수를 이용해서 문자를 좌우 분할하여 나오는 값을 계산하는 방법으로 풀이하였다.
2. extend() 함수는 삽입 대상의 리스트를 풀어서 각각의 요소로 확장해 삽입한다.
3. eval() 함수는 문자열을 파싱하고 파이썬 표현식으로 처리해주는 역할을 한다.
4. 코드가 작동하는 순서를 다음과 같이 정리해보았다.

---