문제) n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수를 출력하라
https://leetcode.com/problems/array-partition/description/
풀이)
예를 들어보자. nums = [1 , 4 ,3 , 2] 라고 할 때, n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 모든 수를 구해보자
min(1,4) + min(3,2) = 1 + 2 = 3
min(1,3) + min(2,4) = 1 + 2 = 3
min(1,2) + min(3,4) = 1 + 3 = 4
위 결과를 봤을 때 합이 최대가 될려면 min(a,b)가 최대가 되어야 하며, 오름차순으로 정렬 후 페어들을 만들 때 min(a,b)의 합이 최대가 된다. 이를 이용하여 풀어보자
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
sum = 0
result = []
#오름차순 정렬
nums.sort()
for n in nums :
result.append(n)
#만일 result가 2개일 경우 min 계산
if len(result) == 2 :
sum += min(result)
result = [] #result 초기화
return sum
위 경우를 살펴보면 항상 짝수번째에 페어의 작은 값이 위치하는 것을 알 수 있다. 리스트의 짝수들만 더해서 구해보자
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
result = []
nums.sort()
for i ,n in enumerate(nums) :
if i % 2 == 0 :
result.append(n)
return sum(result)
위 코드를 슬라이싱을 이용하여 파이써닉하게 풀어보자 .
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
return sum(sorted(nums)[::2])
💡 [::2]는 2칸씩 건너뛰므로 짝수번째를 계산하는 과정과 동일하다
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[LeetCode] - 자신을 제외한 배열의 곱 (1) | 2023.11.15 |
---|---|
[LeetCode] - 주식을 사고팔기 가장 좋은 시점 (0) | 2023.11.14 |
[LeetCode] - 세 수의 합 (0) | 2023.11.14 |
[LeetCode] - 두 수의 합 (0) | 2023.11.14 |
[프로그래머스] Lv1 문제풀이 (1) | 2023.10.09 |