[LeetCode] 561. Array Partition I (배열 파티션 1)

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

2*n 개의 배열에서 n개의 쌍을 만든 후 쌍의 최솟값의 합이 최대가 되는 값을 반환하세요.

✍️ 풀이

---

• 정렬 후 오름차순 풀이

  1. 정렬을 하면 비슷하거나 같은 숫자끼리 쌍을 만들 수 있다.
  2. 쌍을 만들었을 때 첫번째 요소가 min값일수 밖에 없다.
  3. 첫번째 요소를 모두 더한다.

• 파이써닉한 풀이 방법

  1. sorted를 통해 정렬 후 [::2] 리스트 슬라이싱을 이용해 짝수번째 리스트만 남긴다.
  2. 짝수번째 리스트를 sum을 통해 모두 더한다.

🛠 코드

• 리스트를 원소를 앞-뒤로 검사하는 가장 기본적인 풀이방법이다.

---

• 오름차순 코드

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

---

• 좀 더 파이써닉한 풀이

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

📝 정리

---

• 속도는 오름차순 코드가 조금 빨랐다.

🎈 참고

---

Book 링크