분할 정복
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
중요 내용
- nums 안의 모든 수를 반복문으로 돌면서 과반수를 차지하는지 체크한다.
- 시간 초과 에러가 뜬다.
풀이 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와 결과가 나오는 과정은 같으나 연산 횟수를 줄여서 최적화를 하였다.
풀이 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]
중요 내용
- 분할된 리스트에서 과반수를 차지하는 수를 리턴하는 재귀함수로 접근하였다.
풀이 4: 파이썬다운 방식
class Solution:
def majorityElement(self, nums: List[int]) -> int:
return sorted(nums)[len(nums) // 2]
중요 내용
- 정렬한 후에 가운데를 지정하면 반드시 과반수 이상의 수이다.
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
중요 내용
- 재귀함수를 이용해서 문자를 좌우 분할하여 나오는 값을 계산하는 방법으로 풀이하였다.
- extend() 함수는 삽입 대상의 리스트를 풀어서 각각의 요소로 확장해 삽입한다.
- eval() 함수는 문자열을 파싱하고 파이썬 표현식으로 처리해주는 역할을 한다.
- 코드가 작동하는 순서를 다음과 같이 정리해보았다.
Comments