“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/array-partition-i/
이번 문제도 문제 자체를 이해하기 쉽지 않았다. 알고리즘 퀴즈들이 생소해서 그런가보다. 아니면 문해력이 아직 더 자라야 한다든가. 암튼, 2n개의 요소를 가진 배열에서 n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수를 출력해야한다.
지금 봐도 무슨 말인지 모르겠다. 밑의 예를 보자.
Input: nums = [1,4,3,2] -> Output: 4
Input: nums = [6,2,6,5,1,2] -> Output: 9
[1,4,3,2]의 경우, 다음과 같은 페어들이 만들어 질 수 있다.
1: [1,4], [3,2]
2: [1,3], [4,2]
3: [1,2], [4,3]
페어의 min()의 합이라고 했으니까 각각의 결과는 다음과 같다.
1: min(1,4) + min(3,2) = 3
2: min(1,3) + min(4,2) = 3
3: min(1,2) + min(4,3) = 4
그래서 4가 답이 되는 것.
자, 여기까지는 억지로 알겠다. 이걸 코드로 만들려면 우선은 브루트 포스 밖에 떠오르지 않는다. 분명 깔끔한 방식이 있겠지.
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
# 1
# sum = 0
# pair = []
# nums.sort()
# for n in nums:
# pair.append(n)
# if len(pair) == 2:
# sum += min(pair)
# pair = []
# return sum
# 2
# sum = 0
# nums.sort()
# for i, n in enumerate(nums):
# if i % 2 == 0:
# sum += n
# return sum
# 3
return sum(sorted(nums)[::2])#1
입력된 배열을 정리해서 보면 [1,2,3,4]가 되는데, 결국 순서대로(오름차순이든 내림차순이든)의 조합(1,2와 3,4)이 답이라는 것을 알 수 있다. 답을 한참 쳐다봐야 했지만… 그래서 먼저 정렬을 해야한다. 그리고 n[i] + n[i+1]을 반환하면 되겠다.
#2
또 다시 뜯어보면 짝수 번째의 값(nums[0]의 1, nums[2]의 3)을 더하면 된다는 것을 알 수 있다.(난 물론 풀이 보고 앎ㅠ) 그래서 i % 2 에 해당하는 인덱스의 값을 더해서 반환해도 같은 결과다.
#3
파이썬다운 방식이다.(Pythonic Way) 슬라이싱을 이용해 배열의 값들 중에서 2칸 씩 건너 뛴 값을 sum()해서 반환하면 위와같이 한 줄에 가능했다.
이렇게 이해하는 것만 해도 벅차다니.ㅠㅠ