[백준 32344] 유물 발굴 [Java]

문제

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

 

---

풀이

유물들의 위치가 주어졌을 때 동일한 번호의 유물들을 감싸는 최대 크기의 직사각형을 구해야 한다.

이중에서 가장 먼저 발굴하는 유물의 번호와 예상 크기를 구해야 한다.

이를 위해서는 번호가 동일한 유물들의 위치에 대해 최소/최대값을 기록해야 한다.

        Arrays.fill(minRow, R + 1);
        Arrays.fill(minCol, C + 1);
        for (int i = 0; i < N; i++) {
            input = br.readLine().split(" ");
            int id = Integer.parseInt(input[0]);
            int row = Integer.parseInt(input[1]);
            int col = Integer.parseInt(input[2]);

            // Solve
            minRow[id] = Math.min(minRow[id], row);
            maxRow[id] = Math.max(maxRow[id], row);
            minCol[id] = Math.min(minCol[id], col);
            maxCol[id] = Math.max(maxCol[id], col);
        }

이후 반복문을 통해 최대 크기의 직사각형을 구해주고, 만약 유물의 번호가 작은 유물이 있다면 유물 번호를 변경하자.

        long resId = -1, resArea = -1;
        for (int id = 1; id <= N; id++) {
            if(maxRow[id] == 0) continue;
            final long area = (long)(maxRow[id] - minRow[id] + 1) * (maxCol[id] - minCol[id] + 1);
            if (area > resArea || (area == resArea && id < resId)) {
                resArea = area;
                resId = id;
            }
        }

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/practice/32344.java