[leetcode] 561. 배열 파티션 I (Array Partition I)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

 

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

 

입출력 예시

Example 1:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

Example 2:

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

 

생각과정

처음에 n개의 페어이면 중복으로 조합해도 되는거 아니야? 라고 접근하는 바람에 삽질을 엄청했다. 중복으로 조합한다는 말이 뭐냐면,

[1, 3, 4, 2]가 있을 때, [1, 3], [1, 4], [1, 2] 이런식으로......해도 되는게 아닌가....라는 생각을 했다. 문제 이해를 잘 못한 것. 그래서 힌트를 보았고, 다시 제대로 접근을 해보았다.

 

 

n개의 페어는 무조건 짝수이다.
최소값이 가장 큰 두 페어를 합쳐야한다.

1 4 / 2 3 -> 1 + 2 = 3
1 3 / 2 4 -> 1 + 2 = 3
1 2 / 3 4 -> 3 + 1 = 4

잘 보면 순서대로 정렬 되어있는 페어가 가장 크다는 걸 알 수 있다. 그럼 정렬을 해보자

[1, 2, 3, 4]

 

정렬한 배열을 보니 방법이 눈에 보인다. 홀수번째 엘리먼트가 페어 중 가장 작은 값이다.

그럼 배열에서 홀수번째 값만 뽑아서 더한다음 리턴하면 된다. 

 

풀이

# 정렬하기
nums.sort()

print(nums) # [1, 2, 3, 4]

# 순서대로 정렬하면 인덱스 0과 2가 최소값임을 할 수 있다.
# 짝수번째 슬라이싱

print(nums[::2]) # 1, 3

# 합계 구하기

print(sum(nums[::2]))

# =============================
# 함수 정리
# print(sum(nums.sort()[::2])) -> .sort()는 return값이 None이다.

# sorted() 키워드 사용하기
print(sum(sorted(nums)[::2]))

 

슬라이싱에서 n번씩 건너뛰는 방식을 사용하면 편리하다. 

 

크게 설명할 필요 없이 간단한 문법만 있으므로 오늘의 설명은 생략하겠다. 

 

 

---

마치며

유일하게 직접 푼 알고리즘이다. 점프투파이썬을 열심히 공부한 보람이 있네...!