겹치지 않는 축에 평행한(axis-aligned) 직사각형들의 목록 rects가 주어졌다고 가정해 보겠습니다. 우리의 목표는 이 직사각형들이 덮고 있는 공간 안에 있는 정수 좌표의 점 하나를 무작위이면서도 균등한 확률로 선택하는 pick 함수를 작성하는 것입니다.
문제 조건 정리
- 정수 점(integer point)이란 x, y 좌표가 모두 정수인 점을 의미합니다.
- 직사각형의 경계(둘레) 위에 있는 점도 선택 가능한 공간에 포함됩니다.
- i번째 직사각형 rects[i]는 [x1, y1, x2, y2]로 표현되며, [x1, y1]은 왼쪽 아래 모서리, [x2, y2]는 오른쪽 위 모서리의 정수 좌표입니다.
- 각 직사각형의 가로와 세로 길이는 2000을 초과하지 않습니다.
- 1 ≤ rects.length ≤ 100
- pick()은 선택된 점을 정수 좌표 배열 [p_x, p_y] 형태로 반환합니다.
예를 들어 입력이 [1,1,5,5] 하나뿐인 경우, pick()을 세 번 호출하면 [4,1], [4,1], [3,3]과 같은 결과가 출력될 수 있습니다.
풀이 접근 방식: 면적 기반 가중치 선택
핵심 아이디어는 각 직사각형이 포함할 수 있는 정수 점의 개수(면적)에 비례해서 직사각형을 먼저 고르고, 이후 해당 직사각형 내부에서 x, y 좌표를 독립적으로 무작위로 결정하는 것입니다. 이렇게 하면 전체 영역에서 모든 정수 점이 동일한 확률로 선택되도록 보장할 수 있습니다.
알고리즘 단계
- 누적 면적을 저장할 area 배열과 직사각형 정보를 저장할 rect 배열, 총합 sum을 준비합니다.
- 생성자에서 rect에 rects를 복사하고 sum을 0으로 초기화합니다.
- 각 직사각형마다 (|x2 − x1| + 1) × (|y2 − y1| + 1)을 계산해 sum에 더하고, 그 누적값을 area에 차례대로 삽입합니다.
- pick()이 호출되면 randArea를 1 이상 sum 이하의 무작위 값으로 설정합니다.
- area를 순회하며 randArea ≤ area[i]를 만족하는 첫 번째 인덱스 i를 찾습니다. 이 과정 덕분에 면적이 큰 직사각형일수록 더 높은 확률로 선택됩니다.
- 선택된 직사각형의 가로·세로 범위 내에서 dist_x와 dist_y를 각각 무작위로 구합니다.
- (dist_x + rect[i][0], dist_y + rect[i][1])을 반환합니다.
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector <int> area;
vector < vector <int> > rect;
int sum;
Solution(vector<vector<int> >& rects) {
rect = rects;
sum = 0;
for(int i =0 ; i < rects.size(); i++){
int x1 = rects[i][0];
int y1 = rects[i][1];
int x2 = rects[i][2];
int y2 = rects[i][3];
int temp = (abs(x2 - x1) + 1) * (abs(y2 - y1) + 1);
sum += temp;
area.push_back(sum);
}
}
vector<int> pick() {
int randArea = rand() % sum + 1;
int i;
for(i = 0; i < area.size(); i++){
if(randArea <= area[i]) break;
}
int dist_x = rand() % (abs(rect[i][0] - rect[i][2] ) + 1);
int dist_y = rand() % (abs(rect[i][1] - rect[i][3] ) + 1);
return {dist_x + rect[i][0], dist_y + rect[i][1]};
}
};
main(){
vector<vector<int> > v = {{1, 1, 5, 5}};
Solution ob(v);
print_vector(ob.pick());
print_vector(ob.pick());
print_vector(ob.pick());
}
입력
["Solution", "pick", "pick", "pick"]
[[[[1, 1, 5, 5]]], [], [], []]
출력
[2, 3]
[4, 1]
[3, 5]
복잡도 분석
생성자는 n개의 직사각형을 한 번씩 순회하므로 O(n) 시간이 걸립니다. pick()은 최악의 경우 area 배열 전체를 선형 탐색하므로 역시 O(n)입니다. 만약 성능이 중요하다면 area 배열이 오름차순으로 정렬되어 있다는 점을 활용해 이진 탐색(binary search)을 적용함으로써 pick()의 시간 복잡도를 O(log n)까지 개선할 수 있습니다.