[배열] 배열 파티션 1

* leetcode 561. Array Partition 1

 

Q. n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.

# 입력
[1, 4, 3, 2]

# 출력
[4]

# 설명
n은 2가 되면, 최대 값은 4이다.
min(1, 2) + min(3, 4) = 4

---

풀이 1. 오름차순 풀이

최대 min()을 만들기 위해서 내림차순으로 배열을 만들면 항상 최대 min() 페어를 만들 수 있다는 점을 활용한다. 이때, 문제에서 배열 입력값은 2n개일 것이기 때문에 오름차순으로도 같은 결과가 나온다.

def arrayPairSum(nums: List[int]) -> int:
    sum = 0
    pair = []
    nums.sort()
    
    for n in nums:
        pair.append(n)
        
        if len(pair) == 2:
            sum += min(pair)
            pair = []
    
    return sum

 

풀이 2. 짝수 번째 값 계산

위와 같은 논리로 일일이 min()값을 구하지 않아도 짝수 번째 값(index 0부터 시작하므로)을 더하면 같은 결과를 얻을 수 있다.

def arrayPair(nums: List[int]) -> int:
    sum = 0
    nums.sort()
    
    for i, n in enumerate(nums):
        if i % 2 == 0:
            sum += n
    
    return sum
    

 

풀이 3. 파이썬 다운 방식

슬라이싱을 활용하면 파이썬다운 1줄짜리 코드로 해결 가능하다.

def arrayPair(nums: List[int]) -> int:
    return sum(sorted(nums[::2]))