[python] 561. Array Partition

Array Partition - LeetCode

Array Partition - LeetCode

 

배열 파티션 1

주어진 배열에서 2개의 값으로 이루어진 페어를 생성하고 

페어의 값의 최솟값들의 합이 최대가 될 때의 합을 리턴하는 문제 

 

정말로 모든 페어를 구한다 ? -> x 

페어의 최소값들의 합이 최대가 되어야 한다는 조건을 이용하여 페어를 구해보자 

 

풀이

 

오름차순 풀이  

 

2개의 원소를 가진 값들의 최솟값의 합을 구해야 한다 

그러나 모든 원소의 조합을 만들어보지 않고 조건을 만족시키도록 할 수 있다 

 

힌트 

페어의 최소값들이 최대가 되어야 한다 

두 수의 차가 가장 적을 때 최솟값이 최대가 된다 

 

->  [1, 2, 3, 4] 라는 배열이 있을 때 페어의 최솟값은 합은 

(1, 2) (3, 4) 일때 1 + 4로 최대가 된다 

 

이를 코드로 작성하면 다음과 같다 

 

from typing import List
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        # 모든 조합을 구하는 것이 아니라 정렬을 한 뒤 조합을 구하면 된다
        # 최소값이 크도록 조합하는 것이기에 오름차순 정렬을 한 뒤 2개씩 묶으면
        # 최솟값이 최대가 된다. [1, 2, 3, 4] 로 생각해보기

        sum = 0
        pair = []
        nums.sort()

        for n in nums:
            pair.append(n)
            if len(pair) == 2:
                sum += min(pair)
                pair = []

        return sum

        return result

s = Solution()
print(s.arrayPairSum([1,4,3,2]))
print(s.arrayPairSum([6,2,6,5,1,2]))

for 문을 돌며 2개씩 pair 리스트에 삽입하는 방식으로 값을 구할 수 있다. 

 

여기서 특징을 발견할 수 있다

오름차순으로 정렬했을 때 pair의 최솟값은 항상 0, 2, 4,... 의 인덱스 값을 가지는 값들이다 

이를 활용하여 풀이를 확장할 수 있다. 

 

짝수 번째 값 계산

 

모든 pair에 대하여 min 값을 구하지 않아도 짝수 번째 인덱스 값을 가져오면 된다

 

이 방식을 코드로 나타내면 다음과 같다

 

from typing import List


class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        # 위에 작성한 풀이에서 
        # 홀수번째 인덱스 값들의 최대가 되는 최솟값이라는 것을 알게되었다
        sum = 0
        nums.sort()
        for i in range(len(nums)):
            if i % 2 == 0:
                sum += nums[i]

        return sum

        return result

s = Solution()
print(s.arrayPairSum([1, 4, 3, 2]))
print(s.arrayPairSum([6, 2, 6, 5, 1, 2]))

 

여기서 한단계 더 나아가면 파이썬다운 방식을 활용한 풀이를 진행할 수 있다 

 

파이썬다운 방식 

 

인덱스가 짝수일 때의 값의 합 -> 슬라이싱 사용 

 

from typing import List
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        '''
        list 를 n 개의 쌍으로 나누기
        최소값들을 뽑아내기
        그것들의 합 중 가장 큰 값을 반환
        '''

        # 최솟값들의 합이 커지도록
        # 내림차순 정렬해서 개수의 반개의 합 -> 안된다
        # nums = [4, 3, 2, 1] 일 때 4와 3은 큰 수는 맞지만
        # 두 수 중 최소 값이 되지는 않는다 (4는 항상 최대 값이라 더해질 수 없다)

        # 내림 차순으로 정렬한 뒤 홀수 번째 항목들을 더하면 최솟값들의 최대 합이 된다
        
        nums = sorted(nums)
        nums = nums[::2]
        result = sum(nums)

        return result

s = Solution()
print(s.arrayPairSum([1,4,3,2]))
print(s.arrayPairSum([6,2,6,5,1,2]))