[LeetCode/JAVA] 1877. Minimize Maximum Pair Sum in Array

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/

문제 설명

출처 : LeetCode

짝수 길이 배열 nums를 2개의 요소로 쌍을 만듭니다.
요소를 최적으로 쌍으로 만든 후 최소화된 최대 쌍의 합을 반환하세요.

밑의 풀이 방법의 테스트 케이스를 통해 설명하겠습니다. (영어 잘하고 싶다..)

풀이 방법

1. 배열을 정렬한다.
2. 양 끝 값끼리 짝을 이룬다.
3. 이뤄진 짝의 합계들 중 최댓값을 반환한다.

위처럼 다양하게 짝을 만들어 합계를 구하는 수많은 케이스들 중에서 각 합계들의 최댓값을 구할 수 있다. (11, 10, 7)

각 케이스의 최댓값들 중 가장 작은 최솟값인 케이스가 유효한 케이스(7,7,7)이다.

위 그림처럼 마지막 케이스인 (1,6)(2,5)(3,4)가 가장 작으므로 유효한 Pair 케이스를 구할 수 있다.

 

그렇다면, 모든 Pair 케이스를 검사해야 하는가?  X

문제 속에 규칙이 있다.  각 케이스의 최댓값들 중에서 가장 최솟값을 구하려면 배열의 최댓값+최솟값을 더해줘야 한다.

다른 값끼리 더하면 Pair 케이스의 최솟값 조건이 깨진다.

 

우리는 위 예제의 최솟값 케이스는 (7,7,7) 임을 알고 있다.

예를 들어 (1,6)(5,4)(3,2) = 7, 9, 5 = 최댓값(9) 이므로.. 아래 그림처럼 합계를 구해야 한다.

 

위처럼 정렬 후 최솟값과 최댓값을 더해줘야 Pair의 합계 중 최솟값이 된다.

최댓값인 6과 최솟값이 아닌 4를 더하면 11로 최솟값(7)이 아니기 때문에 유효한 Pair조건에 일치하지 않는다.

그리고 (2,5)처럼 한 칸씩 옮긴 포인터들의 값을 더해줘야 하는데,

그 이유는 Pair 합계 중 최솟값보다 같거나 큰 값을 찾아야 하기 때문이다.

 

각 끝 값끼리 더해 최소 Pair 케이스를 찾고,

포인터를 한 칸씩 들어가며 탐색하여 양 끝 값보다 클 수 있는 합계를 찾는 것이다.

max(7, 7, 7) 이므로 7을 반환한다.

 

[2, 4, 4, 4, 4, 5] 케이스를 생각하면 된다.

(7,8,8) →  8  →  최소  →  max(7,8,8)  →  return 8

(6,8,9) →  9

 

내 코드(JAVA)

 

public int minPairSum(int[] nums) {
    int res = 0;
    int sum = 0;
    
    Arrays.sort(nums);

    for(int i=0; i<nums.length/2; i++) {
        sum = nums[i] + nums[nums.length-1-i];
        if(res < sum) res = sum;
    }

    return res;
}

 

글로 표현하려 하니 뭔가 너무 어렵게 느껴지네요.. 주륵 

다양한 테스트 케이스를 이용하여 디버깅해본다면 금방 감을 찾을 수 있을 거라 생각합니다..