문제 설명
m개의 행과 n개의 열로 구성된 격자가 주어지며, 이는 사막 지도를 나타냅니다. 사막 지도의 가장 왼쪽 위칸 좌표는 (0, 0), 오른쪽 아래칸 좌표는 (m-1, n-1)입니다. 이 사막 어딘가에 가로 w, 세로 h 크기의 선인장 구역을 조성하려 합니다. 선인장 구역은 격자 축에 맞춘 연속된 w × h 크기의 부분 격자이며, 회전할 수 없습니다.
비구름은 미리 정해진 순서대로 격자의 여러 칸에 비를 뿌립니다. 이때 빗방울이 처음으로 선인장 구역에 포함된 칸에 떨어졌을 때, 그 시점을 선인장이 처음으로 비를 맞는 순간으로 기록합니다. 당신은 선인장이 가능한 한 늦게 비를 맞도록, 선인장 구역의 위치를 정하려고 합니다.
- 선인장이 비를 맞지 않도록 선인장 구역의 위치를 정할 수 있다면 해당 위치가 가장 우선됩니다.
- 가능한 늦게 비를 맞는 선인장 구역 후보가 여러 개라면 그중 가장 위쪽 행, 그래도 여러 개면 가장 왼쪽 열에 위치한 구역을 선택합니다.
격자의 세로 길이와 가로 길이를 나타내는 정수 m, n, 선인장 구역의 세로 길이와 가로 길이를 나타내는 정수 h, w, 그리고 빗방울이 떨어지는 순서대로 칸의 좌표를 담은 2차원 정수 배열 drops가 매개변수로 주어집니다. 주어진 조건을 만족하는 선인장 구역에 포함된 가장 왼쪽 위칸의 좌표를 정수 배열로 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 1 ≤
m,n≤ 500,000 - 1 ≤
m×n≤ 500,000 - 1 ≤
h≤m - 1 ≤
w≤n - 1 ≤
drops의 길이 ≤m×ndrops[i]는 [r,c] 형태입니다.drops[i]는i + 1번째로 떨어진 빗방울의 좌표를 의미합니다.- 0 ≤
r<m - 0 ≤
c<n drops의 모든 원소는 서로 다른 칸을 나타냅니다.
테스트 케이스 구성 안내
아래는 테스트 케이스 구성을 나타냅니다. 각 그룹은 하나 이상의 하위 그룹으로 이루어져 있으며, 하위 그룹의 모든 테스트 케이스를 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.
| 그룹 | 총점 | 추가 제한 사항 |
|---|---|---|
| #1 | 30% | m ≤ 50, n ≤ 50 |
| #2 | 70% | 추가 제한 없음 |
입출력 예
| m | n | h | w | drops | result |
|---|---|---|---|---|---|
| 4 | 5 | 2 | 2 | [[0, 0], [3, 1], [1, 3], [2, 4], [1, 1], [2, 2], [2, 3], [0, 4]] | [2, 2] |
| 3 | 3 | 1 | 1 | [[0, 0], [0, 1], [0, 2], [1, 0]] | [1, 1] |
| 4 | 6 | 3 | 4 | [[1, 2]] | [0, 0] |
| 4 | 6 | 1 | 2 | [[0, 1], [0, 3], [0, 5], [1, 1], [1, 3], [1, 5], [2, 1], [2, 3], [2, 5], [3, 1], [3, 3], [3, 5]] | [3, 4] |
| 2 | 2 | 2 | 2 | [[0, 0], [0, 1], [1, 1], [1, 0]] | [0, 0] |
| 4 | 4 | 3 | 1 | [[2, 0], [1, 3], [3, 2], [0, 1]] | [0, 2] |
입출력 예 설명
입출력 예 #1
아래 그림은 4 × 5 크기의 지도 격자입니다. 각 칸의 큰 숫자는 빗방울이 떨어지는 순서를, 작은 숫자는 좌표를 나타냅니다.
노란색으로 표시된 구역을 선인장 구역으로 두면, 6번째로 비가 떨어질 때 선인장이 처음 비를 맞게 되며, 이보다 더 늦게 젖도록 하는 배치는 존재하지 않습니다. 따라서 노란색 구역의 가장 왼쪽 위 좌표인 [2, 2]를 return 해야 합니다.
입출력 예 #2
아래 그림은 3 × 3 크기의 지도 격자입니다. 각 칸의 큰 숫자는 빗방울이 떨어지는 순서를, 작은 숫자는 좌표를 나타냅니다.
모든 빗방울이 떨어질 때까지 좌표가 (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)인 칸은 젖지 않습니다. 이 5칸 어디에나 1 × 1 크기의 선인장 구역을 놓을 수 있지만, 그중 가장 위쪽 행, 그리고 가장 왼쪽 열에 해당하는 좌표는 (1, 1)입니다. 따라서 [1, 1]을 return 해야 합니다.
입출력 예 #3
아래 그림은 4 × 6 크기의 지도 격자입니다. 각 칸의 큰 숫자는 빗방울이 떨어지는 순서를, 작은 숫자는 좌표를 나타냅니다.
선인장 구역을 어디에 배치하더라도 첫 번째 빗방울만에 구역이 젖습니다. 따라서 가장 위쪽 행, 그중에서도 가장 왼쪽 열에 위치하는 좌표인 [0, 0]을 return 해야 합니다.
입출력 예 #4
아래 그림은 4 × 6 크기의 지도 격자입니다. 각 칸의 큰 숫자는 빗방울이 떨어지는 순서를, 작은 숫자는 좌표를 나타냅니다.
따라서 [3, 4]를 return 해야 합니다.
입출력 예 #5
아래 그림은 2 × 2 크기의 지도 격자입니다. 각 칸의 큰 숫자는 빗방울이 떨어지는 순서를, 작은 숫자는 좌표를 나타냅니다.
따라서 [0, 0]을 return 해야 합니다.
입출력 예 #6
아래 그림은 4 × 4 크기의 지도 격자입니다. 각 칸의 큰 숫자는 빗방울이 떨어지는 순서를, 작은 숫자는 좌표를 나타냅니다.
따라서 [0, 2]를 return 해야 합니다.
