[파이썬 알고리즘 인터뷰] 배열 - 배열 파티션1
🐍 문제
n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.
- 입력
[1, 4, 3, 2] - 출력
4
n은 2가 되며, 최대 합은 4이다.
min(1, 2) + min(3, 4) = 4
https://leetcode.com/problems/array-partition-i/
🐍 내 풀이 - 오름차순 이용
투 페어의 작은 값들의 합이 가장 커야하므로 작은 값끼리 모아둘 수 있도록 오름차순 정렬 후 순서대로 최솟값을 구하였다.
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
sum: int = 0
if len(nums) == 0:
return sum
nums.sort()
for i in range(0, len(nums), 2):
sum += min(nums[i], nums[i + 1])
return sum
🐍 교재 풀이1 - 오름차순 풀이
똑같이 오름차순 정렬했지만 이유가 다르다. 뒤에서부터 가장 큰 값들을 가져오기 위해 내림차순이 필요했고 간단하게 계산하기 위해 오름차순 정렬했다.
def arrayPairSum(nums: list) -> int:
sum = 0
pair = []
nums.sort()
for n in nums:
# 앞에서부터 오름차순으로 페어를 만들어서 합 계산
pair.append(n)
if len(pair) == 2:
sum += min(pair)
pair = []
return sum
nums = [1, 4, 3, 2]
arrayPairSum(nums) # 4
🐍 교재 풀이2 - 짝수 번째 값 계산
오름차순 정렬했기 때문에 비교하는 두 값의 최솟값은 첫번째 값일것이다, 를 이용하여 min 계산을 줄였다. 내 풀이에서 적용한다면 sum을 더할 때 min계산이 아닌 nums[i]값만 바로 더하면 된다.
def arrayPairSum(nums: list) -> int:
sum = 0
nums.sort()
for i, n in enumerate(nums):
# 짝수 번째 값의 합 계산
if i % 2 == 0:
sum += n
return sum
nums = [1, 4, 3, 2]
arrayPairSum(nums) # 4
🐍 교재 풀이3 - 파이썬다운 방식
def arrayPairSum(nums: list) -> int:
return sum(sorted(nums)[::2])
nums = [1, 4, 3, 2]
arrayPairSum(nums) # 4
Author And Source
이 문제에 관하여([파이썬 알고리즘 인터뷰] 배열 - 배열 파티션1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rudnf003/파이썬-알고리즘-인터뷰-배열-배열-파티션1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)