LeetCode) 배열 파티션

이 문제는 Easy라고 나와 있지만 영어로 되어있어서 나는 문제를 이해하는 곳 부터 막혔다.

간단히 말해서 2n개의 숫자 input이 주어지고 n개의 쌍으로 만들어 각 쌍의 최소값이 가장 크게 만들어 모두 더한 것이 output이다. (간단하지 않다.)

 

처음에는 어떻게 두개의 값을 쌍으로 만들어서 더할까 고민을 많이 했다.

조합 문제인가 했지만 아니였고 아무리 생각해도 두개의 값을 묶는 방법은 떠오르지 않아 답안을 보게 됐다.

 

문제는 간단했다. 두개의 쌍을 만들 필요없이 정렬을 한 후 순서대로 2개의 값을 묶으면 최솟값을 가장 크게 만들 수 있다. 

 

앞으로는 문제가 막힐때에 수학적으로 접근해보는것도 나쁘지 않은 방법 같다.