[알고리즘][배열] - 5. 배열 파티션 1

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/array-partition-i/

n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.

---

[오름차순 풀이]

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        sum = 0
        pair = []
        nums.sort()
        
        for i in nums:
            pair.append(i)
            if len(pair) == 2:
                sum += min(pair)
                pair = [] #핵심! 2개의 요소가 들어왔다면 작은 값을 sum에 주고 pair은 비어준다.
                
        return sum

 

 

 

[짝수 번째 값 계산]

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

        for i in range(len(nums)-1):
            if i % 2 == 0:
                sum += nums[i]
        return sum

• 이 경우 0번째부터 시작하는 list의 index를 정렬해주면 짝수번째 자리는 늘 작은 값이 오기때문에 이를 이용해서 문제를 풀어주면 된다. 

 

 

[slicing을 사용한 방식 - 가장 파이썬 다운 방식]

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

• min( )도 필요 없이 짝수 번째 요소들을 다 더해서 돌려줌. 
• 이때 sort가 아닌 sorted를 사용한 이유는?
  • sort는 리턴값이 없도록 만들어졌다. 
  • sorted는 리턴값이 있도록 만들어졌다. 
  • 따라서 sort는 슬라이싱된 값을 return 해줄 수 없어 sorted를 사용해 값을 구해준다!

 

 

[실행 속도]