99클럽 코테 스터디 23일차 TIL - Array Partition

---

Array Partition

출처 : LeetCode

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.

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.

Constraints:

• 1 <= n <= 104
• nums.length == 2 * n
• -104 <= nums[i] <= 104

---

올바른 풀이

Math.min 연산이 들어간 풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var arrayPairSum = function(nums) {
    // nums를 2개씩 짝지어서 둘 중 작은 수의 합을 구한다.
    // min(a, b)의 값이 최대가 되어야 하므로 큰 수부터 내림차순 정렬하여 2개씩 짝짓는다.
    let score = 0;  // 정답으로 제출할 변수
    const sortedNums = nums.sort((a, b) => b - a);
    for (let i = 0; i < sortedNums.length; i = i + 2) {
        // 2개씩 짝지어야 하므로 인덱스를 2개씩 건너뛰며 반복한다.
        score += Math.min(sortedNums[i], sortedNums[i + 1])
    }
    return score;
};

 

Math.min 연산이 들어가지 않은 풀이

• 내림차순 정렬을 한 후 숫자 2개를 처음부터 짝지었을 때, 어차피 둘 중 오른쪽에 있는 수가 더 작은 수이다.
• 따라서 Math.min 연산을 생략하고 짝수번째 인덱스의 값만 더해도 된다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var arrayPairSum = function(nums) {
    // nums를 2개씩 짝지어서 둘 중 작은 수의 합을 구한다.
    // min(a, b)의 값이 최대가 되어야 하므로 큰 수부터 내림차순 정렬하여 2개씩 짝짓는다.
    let score = 0;  // 정답으로 제출할 변수
    const sortedNums = nums.sort((a, b) => b - a);
    for (let i = 0; i < sortedNums.length; i = i + 2) {
        // 2개씩 짝지어야 하므로 인덱스를 2개씩 건너뛰며 반복한다.
        score += sortedNums[i + 1]
    }
    return score;
};

 

더 효율적인 풀이

• 주어진 nums 배열을 오름차순으로 정렬하고, 짝지어진 인접한 두 숫자 중 첫 번째 숫자를 더하여 최대의 합을 계산한다.

var arrayPairSum = function(nums) {
    // 1. 배열을 오름차순으로 정렬합니다.
    nums.sort((a, b) => a - b);
    
    // 2. 오름차순 정렬된 배열에서 짝지어 `min(ai, bi)`를 최대화합니다.
    let score = 0;
    for (let i = 0; i < nums.length; i += 2) {
        score += nums[i];
    }
    
    return score;
};

 

모든 그래프 문제에 통용되는 풀이

클럽장님이 위 풀이는 이 문제에만 해당하는 풀이라고 말씀하시고, 다른 풀이 방법을 설명해주셨다.

위에서 푼 풀이는 모든 노드와 연결된 중심노드가 1개 있고, 주어진 edges에는 중심노드와 연결된 간선들만 있을 것을 가정하였다.

 

하지만 만약 [1, 2], [2, 3], [4, 2], [4, 5] 이런 식으로 중심노드와 연결되어 있지 않은 간선들이 중간에 섞여 있다고 하면, 위의 풀이로는 중심노드를 구할 수 없다. 왜냐하면 위에 있는 풀이는 맨 앞에서 2개의 간선만 비교하므로, 공통된 노드(중심노드)를 찾지 못하는 경우가 생길 수 있기 때문이다.

 

그래서 정석대로 푸는 방법은, Map(혹은 파이썬에서는 Dictionary)를 사용하여 각 노드의 등장횟수를 카운트하고, 횟수를 비교하는 풀이이다. 

 

등장횟수가 간선 집합의 길이와 같을 때(위 문제에 해당되는 경우) 혹은 등장횟수가 최댓값일 때, 해당 노드를 반환하면 된다.

var findCenter = function(edges) {
    // Map을 사용해서 각 노드의 등장 횟수를 카운트
    const count = new Map();

    for (let i = 0; i < edges.length; i++) {
        let [a, b] = edges[i];
        // 각 노드의 등장 횟수를 1씩 증가
        // if (!count.get(a)) count.get(a) = 0;
        // if (!count.get(b)) count.get(b) = 0;
        count.set(a, ((count.get(a) || 0) + 1))
        count.set(b, ((count.get(b) || 0) + 1))
    }
    // console.log(count)
    // Map(4) { 1 => 1, 2 => 3, 3 => 1, 4 => 1 }

    let maxCount = 0;  // 최댓값
    let centerNode = 0;  // 중심노드

    // 등장 횟수가 edges.length와 같은 노드가 중심 노드
    // 아니면 등장횟수가 가장 많은 걸 중심노드로 판단
    for (let [node, cnt] of count) {
        if (cnt === edges.length) {
            return node;
        }
        if (cnt > maxCount) {
            maxCount = cnt;
            centerNode = node;
        }
    }
    return centerNode;
};

 

느낀점

• 문제를 풀고 바로 넘어가지 말고 한번 더 깊게 생각해보아야겠다고 생각하였다.
• 그래프 문제들은 Map을 활용해서 등장횟수를 count하는 경우가 많으니, 문제를 많이 풀어서 감을 익혀야겠다.