문제 링크

내 코드

생각해보니 adjacent하다는 내용은 필요 없는 정보였다.!!

Solution보니 훨씬 더 간단하다..! (더 빠르고)

• 164ms, 47.46MB

class Solution {
public:
	long long maxMatrixSum(vector<vector<int>>& matrix) {
		// adjacent하다는 정보가 필요 없는 정보임.
		priority_queue<int, vector<int>, greater<int>> pq;

		for (auto& row : matrix) {
			for (auto& v : row) {
				pq.push(v);
			}
		}

		while (!pq.empty()) {
			int first = pq.top(); pq.pop();
			int second = pq.top(); pq.pop();

			if (first + second < -(first + second)) {
				pq.push(-first);
				pq.push(-second);
			}
			else {
				pq.push(first);
				pq.push(second);
				break; // no need to multiply -1;
			}
		}

		long long answer{};
		while (!pq.empty()) {
			int now = pq.top(); pq.pop();
			answer += static_cast<long long>(now);
		}

		return answer;
	}
};

Solution

Approach: Journey From Minus to Plus

• 4ms, 39.18MB
• Complexity
  • Let n be the number of rows and m be the number of columns in the matrix.
  • Time Complexity: $O(n \times m)$
  • Space Complexity: $O(1)$

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        long long totalSum = 0;
        int minAbsVal = INT_MAX;
        int negativeCount = 0;

        for (auto& row : matrix) {
            for (int val : row) {
                totalSum += abs(val);
                if (val < 0) {
                    negativeCount++;
                }
                minAbsVal = min(minAbsVal, abs(val));
            }
        }

        // Adjust if the count of negative numbers is odd
        if (negativeCount % 2 != 0) {
            totalSum -= 2 * minAbsVal;
        }

        return totalSum;
    }
};