- 카카오 테크 블로그
https://tech.kakao.com/posts/814
- 문제 설명
m개의 행과 n개의 열로 구성된 격자가 주어지며, 이는 사막 지도를 나타냅니다. 사막 지도의 가장 왼쪽 위칸 좌표는 (0, 0), 오른쪽 아래칸 좌표는 (m-1, n-1)입니다. 이 사막 어딘가에 가로 w, 세로 h 크기의 선인장 구역을 조성하려 합니다. 선인장 구역은 격자 축에 맞춘 연속된 w × h 크기의 부분 격자이며, 회전할 수 없습니다.
비구름은 미리 정해진 순서대로 격자의 여러 칸에 비를 뿌립니다. 이때 빗방울이 처음으로 선인장 구역에 포함된 칸에 떨어졌을 때, 그 시점을 선인장이 처음으로 비를 맞는 순간으로 기록합니다. 당신은 선인장이 가능한 한 늦게 비를 맞도록, 선인장 구역의 위치를 정하려고 합니다.
선인장이 비를 맞지 않도록 선인장 구역의 위치를 정할 수 있다면 해당 위치가 가장 우선됩니다.
가능한 늦게 비를 맞는 선인장 구역 후보가 여러 개라면 그중 가장 위쪽 행, 그래도 여러 개면 가장 왼쪽 열에 위치한 구역을 선택합니다.
격자의 세로 길이와 가로 길이를 나타내는 정수 m, n, 선인장 구역의 세로 길이와 가로 길이를 나타내는 정수 h, w, 그리고 빗방울이 떨어지는 순서대로 칸의 좌표를 담은 2차원 정수 배열 drops가 매개변수로 주어집니다. 주어진 조건을 만족하는 선인장 구역에 포함된 가장 왼쪽 위칸의 좌표를 정수 배열로 return 하도록 solution 함수를 완성해 주세요.
- 해결 방법
- time 배열
int INF = 1_000_000_000;
int[][] time = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(time[i], INF);
}
for (int i = 0; i < drops.length; i++) {
int r = drops[i][0];
int c = drops[i][1];
time[r][c] = i + 1;
}INF 넣어주고, 비오는 (r,c) 위치에 비오는 순서를 저장했습니다.
- 가로 슬라이딩 최소
int[][] rowMin = new int[m][n - w + 1];
for (int i = 0; i < m; i++) {
Deque<Integer> dq = new ArrayDeque<>();
for (int j = 0; j < n; j++) {
// 윈도우 범위 벗어난 인덱스 제거
while (!dq.isEmpty() && dq.peekFirst() <= j - w) {
dq.pollFirst();
}
// 현재 값보다 큰 값 제거
while (!dq.isEmpty() && time[i][dq.peekLast()] >= time[i][j]) {
dq.pollLast();
}
dq.addLast(j);
// 결과 기록
if (j >= w - 1) {
rowMin[i][j - w + 1] = time[i][dq.peekFirst()];
}
}
}rowMin은 각 행에서 길이 w인 구간을 한 칸씩 이동하면서, 각 구간의 최소값을 저장하는 배열이다.
이때 deque에는 인덱스를 저장한다. 현재 위치 j를 기준으로, 윈도우 범위를 벗어난 인덱스는 앞에서 제거하고, 현재 값보다 크거나 같은 값들은 뒤에서 제거한다.
그런 다음 현재 인덱스를 deque에 추가한다.
이 과정을 반복하다가 구간의 길이가 w에 도달하면, deque의 맨 앞에 있는 인덱스가 해당 구간의 최소값을 가리키므로 이를 rowMin에 기록한다.
- 세로 슬라이딩 최소 (h)
int[][] finalMin = new int[m - h + 1][n - w + 1];
for (int j = 0; j < n - w + 1; j++) {
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < m; i++) {
while (!dq.isEmpty() && dq.peekFirst() <= i - h) {
dq.pollFirst();
}
while (!dq.isEmpty() && rowMin[dq.peekLast()][j] >= rowMin[i][j]) {
dq.pollLast();
}
dq.addLast(i);
if (i >= h - 1) {
finalMin[i - h + 1][j] = rowMin[dq.peekFirst()][j];
}
}
}3번도 마찬가지로 아까 기록한 rowMin 배열을 슬라이딩 윈도우를 사용하여서 구한다.
- max(min) 찾기
int bestVal = -1;
int ansR = 0, ansC = 0;
for (int i = 0; i <= m - h; i++) {
for (int j = 0; j <= n - w; j++) {
int val = finalMin[i][j];
if (val > bestVal) {
bestVal = val;
ansR = i;
ansC = j;
}
}
}
return new int[]{ansR, ansC};
}
bestVal 을 찾아 ansR, ansC 를 기록해 반환한다
