C++로 풀어보는 범위 덧셈 II 문제: 최댓값 개수 구하기

문제 이해하기

m × n 크기의 행렬 M이 있으며, 초기에는 모든 원소가 0으로 채워져 있다고 가정해 봅시다. 그리고 여러 개의 갱신(update) 연산이 주어집니다.

각 연산은 2차원 배열의 형태로 표현되며, 두 개의 양수 a와 b를 담고 있습니다. 이 연산은 행렬에서 i가 0부터 a-1까지, j가 0부터 b-1까지인 모든 위치 M[i][j]의 값을 1씩 증가시킨다는 의미입니다.

모든 연산을 수행한 후, 행렬에 존재하는 최댓값의 개수를 구하는 것이 우리의 목표입니다.

예제 살펴보기

예를 들어 m = 3, n = 3이고 operations = [[2,2],[3,3]]이라면, 출력은 4가 됩니다.

초기 행렬은 다음과 같습니다.

첫 번째 연산 [2,2]를 수행하면:

두 번째 연산 [3,3]을 수행하면:

최종 행렬에서 최댓값은 2이며, 이 값은 총 4개 존재합니다. 따라서 정답은 4입니다.

접근 방법: 핵심 아이디어

이 문제는 직관적으로 접근하면 됩니다. 모든 연산은 항상 좌상단(0,0)부터 시작하여 a×b 크기만큼 영역을 덮습니다. 따라서 모든 연산에 공통으로 포함되는 영역, 즉 각 연산의 a와 b 중 최솟값들의 곱이 곧 최댓값의 개수가 됩니다.

알고리즘은 다음과 같습니다.

• minR := m, minC := n 으로 초기화합니다.

• ops 배열의 각 연산 op에 대해:

  • minR := min(minR, op[0])

  • minC := min(minC, op[1])

• minR * minC 를 반환합니다.

연산 배열이 비어 있는 경우에는 어떤 갱신도 일어나지 않으므로, 전체 행렬이 0으로 유지되어 m × n이 정답이 됩니다. 위 초기화 방식은 이 경우도 자연스럽게 처리합니다.

시간 복잡도는 O(k)이며(k는 연산의 개수), 공간 복잡도는 O(1)로 매우 효율적입니다.

C++ 구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maxCount(int m, int n, const vector<vector<int>>& ops) {
        int minR = m;
        int minC = n;
        for (const auto& op : ops){
            minR = min(minR, op[0]);
            minC = min(minC, op[1]);
        }
        return minR * minC;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{2,2},{3,3}};
    cout << (ob.maxCount(3,3,v));
}

입력

3,3,{{2,2},{3,3}}

출력

4

마무리

범위 덧셈 II 문제는 겉보기에는 행렬 조작처럼 복잡해 보이지만, 갱신 연산이 항상 원점에서 시작한다는 특징을 파악하면 단 한 번의 순회로 해결할 수 있는 elegant한 문제입니다. 실제 행렬을 만들어 시뮬레이션할 필요 없이 최솟값 계산만으로 O(1) 추가 공간에 답을 구할 수 있다는 점이 핵심 포인트입니다.