문제 개요
높이 h, 너비 w를 가진 직사각형 케이크가 있다고 가정해 봅시다. 그리고 두 개의 정수 배열이 주어지는데, horizontalCuts[i]는 케이크 상단에서 i번째 수평 절단선까지의 거리를, verticalCuts[j]는 케이크 왼쪽 변에서 j번째 수직 절단선까지의 거리를 의미합니다.
목표는 주어진 모든 위치에서 케이크를 잘랐을 때 생기는 조각 중 가장 넓은 면적을 구하는 것입니다. 결과값이 매우 커질 수 있으므로, 109 + 7로 나눈 나머지를 반환해야 합니다.
예시
예를 들어 h = 5, w = 4, horizontalCuts = [1, 2, 4], verticalCuts = [1, 3]이라고 합시다. 빨간 선이 수평 및 수직 절단선을 나타내며, 케이크를 모두 자른 후 초록색으로 표시된 조각이 최대 면적을 가집니다. 따라서 출력값은 4가 됩니다.
접근 방법
이 문제의 핵심 아이디어는 매우 단순합니다. 최대 면적의 조각은 반드시 '인접한 수평 절단선 사이의 가장 넓은 간격'과 '인접한 수직 절단선 사이의 가장 넓은 간격'이 만나는 지점에 존재합니다. 따라서 다음 단계로 해결할 수 있습니다.
- 오버플로우를 방지하기 위해 mul(a, b) 함수를 정의합니다. 이 함수는 ((a mod m) * (b mod m)) mod m을 반환합니다.
- 메인 메소드에서 h, w, 배열 hh, 배열 vv를 입력받습니다.
- 배열 hh와 vv를 오름차순으로 정렬합니다.
- hh의 맨 앞에 0을 삽입하고 맨 뒤에 h를 추가합니다. 마찬가지로 vv의 맨 앞에 0을 삽입하고 맨 뒤에 w를 추가합니다. 즉, 케이크의 경계선도 하나의 절단선처럼 취급하는 것입니다.
- a := 0, b := 0으로 초기화합니다.
- i := 1부터 hh의 크기 미만까지 반복하며, a를 a와 hh[i] - hh[i-1] 중 더 큰 값으로 갱신합니다.
- i := 1부터 vv의 크기 미만까지 반복하며, b를 b와 vv[i] - vv[i-1] 중 더 큰 값으로 갱신합니다.
- mul(a, b)를 반환합니다.
이 알고리즘의 시간 복잡도는 정렬에 지배적이므로 O(n log n + m log m)이며, 추가 공간은 상수 수준으로 매우 효율적입니다.
C++ 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef long long int lli;
class Solution {
public:
lli mul(lli a, lli b){
return ((a % mod) * (b % mod)) % mod;
}
int maxArea(int h, int w, vector<int>& hh, vector<int>& vv) {
sort(hh.begin(), hh.end());
sort(vv.begin(), vv.end());
hh.insert(hh.begin(), 0);
hh.push_back(h);
vv.insert(vv.begin(), 0);
vv.push_back(w);
int a = 0;
int b = 0;
for (int i = 1; i < hh.size(); i++) {
a = max(a, hh[i] - hh[i - 1]);
}
for (int i = 1; i < vv.size(); i++) {
b = max(b, vv[i] - vv[i - 1]);
}
return mul(a, b);
}
};
main(){
Solution ob;
vector<int> v = {1,2,4}, v1 = {1,3};
cout << (ob.maxArea(5,4,v,v1));
}
입력
5,4,{1,2,4}, {1,3}출력
4
마무리
이 문제는 정렬 후 인접 요소 간 최대 간격만 찾으면 되는 직관적인 그리디 유형의 문제입니다. 경계값(0과 h, w)을 배열에 포함시키는 처리만 잊지 않으면 깔끔하게 해결할 수 있습니다.