leetcode 561 (easy)

문제

https://leetcode.com/problems/array-partition-i/submissions/

내 풀이 1

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        answer = sum([nums[i] for i in range(len(nums)) if i % 2 == 0]) 
        
        return answer

먼저 모든 경우를 다 비교해 볼 경우, (2n C 2) / 2 가 되어 O(n^2) 이 나온다.
인풋이 10^4 이기 때문에 시간초과가 날 것 같아 더 빠른 방법을 생각해 보았다.

만약 최소값을 구하는것이었으면, 그냥 정렬하고 앞에 절반의 합을 구하면 될 것이다.
최대값도 마찬가지로 일단 정렬을 해놓고 거기서 정해진 규칙대로 실행해야겠다는 생각이 들었는데,
어떻게 해야 min들의 최대가 될 지 규칙이 바로 생각나지 않았다.

주어진 테스트케이스로 직접 해보면서 생각하다보니 (1,2) (3,4) (5,6) 이런식으로 순서대로 묶을 경우에
최대값이 될 것 같았다.

결과 1

풀이 2

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

조금 더 파이썬스러운 간결한 코드로 바꿔보았따. 논리는 똑같다.

결과 2