[LeetCode]배열 파티션Ⅰ

문제

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.

코드

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {

   sort(nums.begin(), nums.end());
	int isright = false;
	int sum = 0;
	for (int i : nums)
	{
		if (isright)
		{
			isright = false;
			continue;
		}
		sum += i;
		isright = true;
	}
    return sum;

    }
};

풀이

1.

sort(nums.begin(), nums.end());

• 작은 순서대로 페어를 생각하기 위한 정렬

2.

	for (int i : nums)
	{
    	//1.
		if (isright)
		{
			isright = false;
			continue;
		}
        //2.
		sum += i;
		isright = true;
	}
    return sum;

    }

1. if문으로 한 페어에서 오른쪽 값(큰 값)인지 확인, 크다면 if문을 false로 통과 할 수 있게 만든 뒤, continue.

2. 한 페어의 왼쪽의 값을 sum에 더해준다. 다음 반복자의 값을 sum에 더하지 않기 위해 bool데이터인 isright를 true로 할당한다.

결과

Runtime 58 ms / Memory 28.2 MB
https://leetcode.com/problems/array-partition/submissions/887944712/

---

https://leetcode.com/problems/array-partition/