LeetCode 561.Array Partition I (Python3)

 

안녕하세요. 죠쵸입니다

LeetCode 561번 문제를 통해서, Python 기초문법 및 알고리즘을 이야기 하려고 합니다.

leetcode.com/problems/array-partition-i

Array Partition I - LeetCode

 

#LeetCode 561.Array Partition I (Description)

 

2n개의 정수 배열이 주어지면, n개의 Pair를 만들고, 각 Pair의 최소값 min(ai, bi)을 더했을 때, 해당 최소값의 합이 가장 큰 수를 구하는 문제입니다. 문제는 복잡해 보일 수 있지만 풀이는 간단한 난위도 "Easy"에 해당하는 문제 입니다.

 

 

#LeetCode 561.Array Partition I (Solution)

 

각 Pair의 min(ai, bi) 최대합을 구하기 위해서 우선 정렬이 되어야 합니다. 정렬된 순서안에서 최소값들을 더했을 때, 이 문제에서 원하는 최대값을 얻을 수 있습니다. 정렬된 리스트에서 각 Pair를 최소값을 구하는 것은 짝수의 위치(0, 2 ...)의 값을 추출하는 것과 같습니다. 리스트를 정렬하기 위해서 Python List에서 제공하는 sort() 함수를 통해서 간단히 정렬을 할 수 있습니다.

 

예를 들면 [ 1, 2, 3, 4 ]의 리스트에서 min(1,2) => 1, min(3,4) =>3 이 각 Pair의 최소값에 해당합니다. 0, 2, 4 .... 짝수번째 인덱스를 구하기 위해서는, enumerate() 함수를 이용해서 쉽게 구할 수 있습니다. Python의 연산자 중 % 는 나눗셈의 나머지 값을 구할 때 사용됩니다. 아래의 코드와 같이 2로 나누었을 때, 나머지가 0이 되는 수가 짝수에 해당함으로, % 연산자는 홀수, 짝수를 구분하는데 자주 사용이 됩니다.  

 

코드보다 설명이 더 길었네요.. 코드를 보시면 더욱 이해하기 쉬울 것으로 생각됩니다.

 

    def arrayPairSum1(self, nums: list) -> int:
        sum = 0
        nums.sort()
        for i, n in enumerate(nums):
            if i % 2 == 0:
                sum += n

        return sum

 

방문해 주셔서 감사합니다. 여러분의 공감하기(♥), 댓글과 구독은 저에게 힘이 됩니다.

이상으로 죠쵸였습니다.