BOJ 14658 하늘에서 별똥별이 빗발친다

https://www.acmicpc.net/problem/14658

문제

“오빠! 나 얼마만큼 사랑해?”

“널 위해서라면 저기 저 하늘의 별이라도 따다 줄 수 있어. 지금 따줄까?”

“에이, 거짓말!”

“정말이야. 한 번 봐봐!”

욱제는 하늘을 발로 차버렸다. 그랬더니 정말 별이 떨어졌다. 그런데, 정말로 별이 지구로 떨어지기 시작했다. 욱제는 지구를 지키는 정의의 용사가 되기로 결심했다.

“자기야, 나 세계를 지키고 올게. 꼭 돌아올 테니 조금만 기다려줘.”

지구의 파괴를 막기 위해서는 지표면에 떨어지는 별똥별의 수를 최소화해야 한다. 욱제는 커다란 네모난 L*L 크기의 트램펄린을 준비했다. 별똥별이 어디로 떨어질지는 이미 알고 있기 때문에, 욱제는 이 트램펄린으로 최대한 많은 별똥별을 우주로 튕겨낼 계획이다. 하지만 학교 예산으로 트램펄린을 구매하는 욱제는 이 긴급한 와중에도 예산 심의 통과를 기다리느라 바쁘다!

욱제를 도와 세계를 구하자. 최대한 많은 별똥별을 튕겨내도록 트램펄린을 배치했을 때, 지구에는 몇 개의 별똥별이 부딪히게 될까? (별똥별이 떨어지는 위치는 겹치지 않으며 별똥별은 트램펄린의 모서리에 부딪혀도 튕겨나간다!) 트램펄린은 비스듬하게 배치 할 수 없다.

---

입력

첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 뜻한다. 이후 K개의 줄에 걸쳐 별똥별이 떨어지는 위치의 좌표 (x, y)가 주어진다. (0 ≤ x ≤ N, 0 ≤ y ≤ M)

---

출력

욱제가 트램펄린으로 최대한 많은 별똥별을 튕겨낼 때, 지구에 부딪히는 별똥별의 개수를 출력한다.

---

예제 입력 1

12 10 4 7
2 4
7 3
3 1
5 6
4 7
12 10
8 6

예제 출력 1

3

---

코드

N과 M이 최대 500,000까지 되기 때문에 무작정 트램펄린을 모든 위치에 놓으며 검사할 수는 없었다. (500,000 ^ 2 칸을 모두 돌아니며 최대 100개의 별똥별이 트램펄린의 범위에 들어가는지 검사해야 하기 때문에 이것을 전부 검사할 수는 없다.)

따라서 모든 별동별의 x좌표와 y좌표를 각각 저장하고, x좌표와 y좌표가 조합된 모든 위치에 트램펄린을 놓아 검사했다.

다른 코드들을 살펴보니, 나처럼 x와 y좌표를 나눠서 저장하지 않고 이중 for문으로 두 별동별을 순회하며 각각의 별동별의 x좌표와 y좌표를 조합해 검사한 경우도 있었다.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static int L;
    static Point[] shootingStars;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        shootingStars = new Point[K];
        Set<Integer> xIndices = new HashSet<>();
        Set<Integer> yIndices = new HashSet<>();
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            shootingStars[i] = new Point(x, y);
            xIndices.add(x);
            yIndices.add(y);
        }

        int maxStarsInBoundary = Integer.MIN_VALUE;

        for (int xIndex: xIndices) {
            for (int yIndex: yIndices) {
                int countStars = countStarsInBoundary(xIndex, yIndex);
                maxStarsInBoundary = Integer.max(maxStarsInBoundary, countStars);
            }
        }

        System.out.println(K - maxStarsInBoundary);
    }

    static int countStarsInBoundary(int x, int y) {
        int count = 0;
        int xBoundary = x + L;
        int yBoundary = y + L;

        for (Point star: shootingStars) {
            if(star.x >= x && star.x <= xBoundary && star.y >= y && star.y <= yBoundary) {
                count++;
            }
        }

        return count;
    }
}