[구름 알고리즘 먼데이 챌린지] Week6 : 4. 경쟁 배타의 원리

문제

경쟁 배타의 원리란 생태학의 원리 중 하나로, 같은 영역에서 같은 생태적 지위를 차지하는 두 종은 분서를 제외하고는 공존할 수 없다는 것이다. 쉽게 말해서, 둘 이상의 종이 존재한다면 서로 경쟁하여 생존에 유리한 하나의 종만이 살아남는다.

 

하지만 구름이가 설계한 메타버스의 경쟁 배타의 원리는 이와 조금 다른데, 둘 이상의 종이 아닌 정확히 K개의 종이 공존할 때만 경쟁이 일어난다. 종의 수가 K보다 작거나 많다면 경쟁이 일어나지 않고 공생하며 살아간다.

 

구름이의 메타버스는 가로 세로 크기가 1,000인 정사각형 모양이다. 현재 구름이의 메타버스에는 생태적 지위가 같은 

N종의 생물이 있고, 각 종의 서식지는 메타버스의 테두리에 평행한 직사각형 모양으로 나타내어진다.

 

메타버스의 생태계 지도가 주어졌을 때, 경쟁 배타의 원리가 일어나는 영역의 총 넓이를 구해보자.

---

입력

첫 번째 줄에는 두 정수 N과 K (1 <= K <= N <= 100,000)가 주어진다. 

N은 구름이의 메타버스에 살고 있는 종의 수이고, 

K는 경쟁이 일어나는 종의 수이다.

두 번째 줄부터 N개의 줄에 걸쳐 각 종의 서식지를 나타내는 네 개의 정수 x1,y1,x2,y2가 공백으로 구분되어 주어진다. 

(x1,y1)은 서식지의 좌측 상단 꼭짓점, 

(x2,y2)는 서식지의 우측 하단 꼭짓점의 좌표를 의미한다. (x1 < x2, y1 < y2)

 모든 좌표는 0이상 1,000이하이다.

---

문제를 보고 2차원 배열에서의 누적합 문제라고 생각했다.

단순하게 네 좌표를 입력 받을 때마다 해당 영역의 좌표를 증가시켜주어도 예시의 테스트 케이스들은 통과하지만,

제출 시 히든 테스트 케이스에서 타임아웃이 발생하는 것을 볼 수 있다.

 

누적합 알고리즘에 대해에서는 좀 오래 전에 알고 있었는데 프로그래머스 2022 KAKAO BLIND RECRUITMENT 파괴되지 않은 건물 문제를 풀면서 확실하게 공부하였다.

 

꽤 빈번하게 출제 되는 유형이고 한번 익혀두면 어렵지 않게 응용할 수 있는 알고리즘이기 때문에 누적합을 처음 접하는 사람들은 이번 기회에 확실히 알아가는 시간을 가지길 추천한다.

 

누적합에 대한 설명은 아래에 첨부한 블로그에서 자세하게 설명하고 있다.

여기

[Programmers] 파괴되지 않은 건물 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT

#include <iostream>

using namespace std;

int N, K, board[1001][1001], ans;
int minX = 1001, minY = 1001 , maxX, maxY;

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> K;
	int x1, y1, x2, y2;
	for (int i = 0; i < N; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 < minX) minX = x1;
		if (y1 < minY) minY = y1;
		if (x2 > maxX) maxX = x2;
		if (y2 > maxY) maxY = y2;
		board[y1][x1]++;
		board[y2][x2]++;
		board[y1][x2]--;
		board[y2][x1]--;
	}
	for (int i = minY; i < maxY; i++) 
		for (int j = minX; j < maxX; j++) 
			board[i][j + 1] += board[i][j];

	for (int j = minX; j < maxX; j++) 
		for (int i = minY; i < maxY; i++) 
			board[i + 1][j] += board[i][j];

	for (int i = minY; i < maxY; i++)
		for (int j = minX; j < maxX; j++)
			if (board[i][j] == K) ans++;

	cout << ans;
}