++/자료구조&알고리즘

[Leetcode] 561. Array Partition

writtenbyrla 2023. 12. 19. 14:13

✅ 문제 - 배열 파티션

💡 문제 포인트
숫자 배열 nums를 2개씩 파티셔닝 해서, 그룹별 최솟값을 더했을 때 합이 가장 큰 경우 그 합을 반환
nums는 짝수 개수로 이루어져 있음

 
 
 


 

 나의 코드

💡 나의 Point

1. 리스트 오름차순 정렬
2. 2개씩 파티셔닝 한다고 쳤을 때 오름차순 되어 있기 때문에 파티션 중 첫 번째 값(최솟값)끼리 더하면 합이 최대로 나옴
3. 리스트 인덱스가 0, 2, 4, 6인 경우끼리 더해주기
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        sum=0

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


파이썬에서 for문 돌릴 때 i 증가 범위를 2로 잡아주면 된다
range(start, end, 증가 단위) 라고 생각하면 쉬움!
이 경우 런타임은 222ms, 메모리는 20.7MB
 
 


 

  풀이 - 슬라이싱 활용

내가 푼 방식이랑 아주 비슷한데 for문을 돌리지 않고 그냥 정렬과 동시에 2씩 건너뛰면서 총합을 구하는 방법이다.

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


for문 돌릴때보다 성능향상을 더 기대했는데 결과는 런타임 227ms 메모리 20.7MB로 시간만 조금 더 늘었다.