LeetCode 561. Array Partition

배열 안의 숫자들 중 페어의 최솟값을 합한 수가 가장 큰 수를 구하는 문제이다.

[1, 3, 4, 2] 에서 2개씩 묶었을 때 가장 큰 수가 나오려면 (1, 2), (3, 4) 이고 이 쌍의 최솟값의 합 중 최댓값은 1 + 3 = 4 이다

풀이

나의 풀이

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        answer = 0
        for i in range(len(nums)//2):
            answer += nums[i*2]		// min을 하지 않는 이유는 이미 정렬된 것이기 때문에
        retrun answer

일단 배열 안의 숫자를 정렬(오름차순)을 하는 것이 가장 먼저라는 생각이 들었다.

그렇게 정렬된 숫자들을 앞에서부터 2개씩 묶는다면 최솟값들의 합 중 최댓값이 나올 것이라 생각하였고, 정답이었다.

 

하지만 여기서 함정은 for 문의 range 방법이었던 것 같다.

아래는 내가 사용한 방법 + 다른 방법들이다.

 for i in range(len(nums)//2):
 	// i의 값이 절반까지라면
    // nums[i*2]를 해야 한다. i*2 = 0, 2, 4, 6...
    
 for i in range(0, len(nums), 2):
 	// range자체에서 i의 값을 0, 2, 4, 6....로 할당하는 방식이다.
    
 for i in range(len(nums)/2):
 	// 처음에는 그냥 나누려 하였지만 나눈값이 float이므로 range 사용이 불가하다.

결과값

---

enumerate 사용

def arrayPairSum2(self, nums: List[int]) -> int:
    nums.sort()
    answer = 0

    for i, n in enumerate(nums):
        if i % 2 == 0:
            answer += n
    return answer

저번에 배웠던 in enumerate을 사용하는 방법이다.

if i % 2 == 0 은 정렬된 배열에서 0, 2, 4, 6 ... 번째 원소를 구하는 식이다.

결과값2

---

슬라이싱 사용

def arrayPairSum3(self, nums: List[int]) -> int:
    return sum(sorted(nums)[::2])

sorted()로 정렬 한 뒤  [::2]로 짝수번째(0, 2, 4, 6...) 원소들을 sum()으로 다 더한다.

결과값3

런타임에서 차이가 없고, 메모리가 약간 줄어들었다.