[백준][Java] 11997 - Load Balancing (Silver)

1. 문제 정보

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

11997번: Load Balancing (Silver)

난이도 : G3

유형 : 좌표압축, 누적합

시간 : O(N^2)

---

2. 문제 풀이

x와 y 좌표값의 크기는  최대 1_000_000 백만이므로 좌표압축을 하지 않으면 시간초과가 발생한다.

입력되는 좌표마다 x 와 y를 따로 분리한 뒤 set을 통해 저장한다.

 

set에 저장할 때 오름차순으로 정렬해야 하므로 TreeSet을 이용한다.

오름차순으로 정렬하는 이유는 좌표마다 원점과의 상대적인 위치를 알아야 하기 때문이다.

 

압축과정을 끝내면 setX의 개수는 최대 1000개이고 setY도 최대 1000개가 된다.

 

좌표 압축 전 (1_000_000) X (1_000_000) 인 테이블의 크기를

좌표 압축 후 (1_000) X (1_000)로 테이블의 크기를 줄일 수 있게 되었다.

 

이후는 일반적인 2차원 누적합 기법을 사용하면 된다.

누적합 테이블을 생성한 뒤 

 

마지막으로 

(0 <= i <= setX), (0 <= j <= setY)

구역을 나누는 십자선의 중심인 (i, j)를 움직이면서 탐색하면 된다.

---

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static final StringBuilder sb = new StringBuilder();
    public static StringTokenizer st;

    int N;
    int[][] coordinates;
    TreeSet<Integer> treeSetX;
    TreeSet<Integer> treeSetY;
    HashMap<Integer, Integer> relativeX;
    HashMap<Integer, Integer> relativeY;
    int[][] compressedBoard;
    int[][] prefixSum;
    int res;

    private int getPrefixSumValue(int x1, int y1, int x2, int y2) {

        return prefixSum[x2][y2] - prefixSum[x2][y1] - prefixSum[x1][y2] + prefixSum[x1][y1];
    }

    private void solution() throws IOException {

        N = Integer.parseInt(br.readLine());
        coordinates = new int[N][2];
        treeSetX = new TreeSet<>();
        treeSetY = new TreeSet<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            coordinates[i][0] = x;
            coordinates[i][1] = y;
            treeSetX.add(x);
            treeSetY.add(y);
        }

        relativeX = new HashMap<>();
        int count = 0;
        for (int x : treeSetX) {
            relativeX.put(x, count);
            count++;
        }

        relativeY = new HashMap<>();
        count = 0;
        for (int y : treeSetY) {
            relativeY.put(y, count);
            count++;
        }

        int row = relativeX.size();
        int col = relativeY.size();
        compressedBoard = new int[row][col];
        for (int i = 0; i < coordinates.length; i++) {
            compressedBoard[relativeX.get(coordinates[i][0])][relativeY.get(coordinates[i][1])]++;
        }

        prefixSum = new int[row + 1][col + 1];
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                prefixSum[i][j] = compressedBoard[i - 1][j - 1] + prefixSum[i][j - 1] + prefixSum[i - 1][j] - prefixSum[i - 1][j - 1];
            }
        }

        res = Integer.MAX_VALUE;
        for (int i = 0; i <= row; i++) {
            for (int j = 0; j <= col; j++) {
                int areaA = getPrefixSumValue(0, 0, i, j);
                int areaB = getPrefixSumValue(0, j, i, col);
                int areaC = getPrefixSumValue(i, j, row, col);
                int areaD = getPrefixSumValue(i, 0, row, j);
                int max = Math.max(areaA, Math.max(areaB, Math.max(areaC, areaD)));
                res = Math.min(res, max);
            }
        }

        System.out.println(res);
    }

    public static void main(String[] args) throws IOException {

        Main main = new Main();
        main.solution();
    }
}