Array Partition

나의 논리

처음에는 O(n^2) 시간이 걸리는 반복문을 써서 브루트포스로 해봐야하나? 싶었는데 그것도 아니었다. 반복문으로 풀려면 최악의 상황에서 O(n^2)이상의 시간복잡도를 가지는 로직을 구현해야 할꺼같아서
생각의 방향성을 달리해 어떤 규칙이 있을것이라고 생각해봤다.

그랬더니 리스트의 원소들을 정렬했을때 인접원소끼리 묶는게 보였다.
그럴법도한게 n개의 pair들의 min값을 구하는데 원소를 정렬했을때
0번째 인덱스의 원소와 마지막 인덱스의 원소가 엮여버리면 0번째 인덱스가 선택이 된다.

따라서 작은 원소는 그냥 작은 원소끼리 묶여 지도록 하고 큰 원소끼리 묶여지도록 하는것이 가장 좋아보였다.

def arrayPairSum(self, nums: List[int]) -> int:
        
        nums.sort()

        sum = 0
        for i in range(0,len(nums),2):
            sum += min(nums[i],nums[i+1])
    
        return sum

정답논리

좀 더 파이써닉한 코드가 있다.

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

sum()

• 리스트를 받으면 리스트의 원소들의 합을 반환

sorted()

• 리스트를 받으면 정렬된 리스트를 반환