[리트코드] Array Partition 1(python)

리트코드, Array Partition 1_배열 분할

 

TL;DR

• 문제에 원하는 조건에 맞게 배열을 조작할 수 있는지

문제 분석

1. 길이가 2n인 정수 배열 nums가 주어진다.
2. nums에서 만들 수 있는 n개 쌍에서 각 쌍의 최소값의 합이 최대가 될 때의 값을 반환한다.

 

- 1 ~ 2 : 해결해야 하는 문제 조건에 대해서 말하고 있다. 입출력 형태를 통해 어떤 문제인지 더 잘 이해할 수 있다.

입출력 형태

입출력 예시

 

- nums : 정수 배열이 주어진다.

- 예시 1

    - 만들 수 있는 쌍의 모든 경우는 explanation에서 보이는 바와 같다.

    - 각 쌍에서 최소값의 합이 최대가 되는 경우는 3번 (1, 2), (3, 4)로 만들었을 때이다.

- 예시 2

    - 만들 수 있는 쌍 중 쌍의 최소값의 합이 최대가 되는 경우는 (2, 1), (2, 5), (6, 6)이고, 그 때의 합은 9이다. 따라서 9를 반환한다.

    - 쌍을 다시 정렬해보면 (1, 2), (2, 5), (6, 6)이 됬을 때이다.

    - 쌍의 최소값의 인덱스는 0, 2, 4로 짝수번째 인덱스의 값을 더하면 된다. 

    - 이를 통해 주어진 배열 nums를 오름차순으로 정렬하고 짝수번째 항을 골라 더할 때가 값이 최대임을 유도해낼 수 있다.

풀이

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

 

- 풀이는 매우 간단하다. 주어진 배열을 먼저 정렬한 후 0번 인덱스부터 짝수번째의 원소를 더하면 된다.

- 슬라이싱을 통해 0번 인덱스부터 짝수 번째 원소를 조회하여 더할 수 있다.