[9063] 대지

난이도: ★☆☆☆☆ • solved on: 2025-07-22

---

문제 요약

• 문제 유형: 구현, 기하
• 요구사항: 주어진 N개의 좌표를 모두 포함하는 가장 작은 직사각형의 넓이를 구해야 한다.

---

사용 개념

1. 자료구조

   • 2차원 배열 (int[][]) – 최솟값/최댓값 좌표 추적용

2. 알고리즘/기법

   • 최댓값/최솟값 갱신
   • 예외 케이스 처리 (N = 1일 때 넓이 0)

3. 핵심 키워드

   • 직사각형 넓이 구하기
   • 최소/최대 범위 설정

---

풀이 아이디어

1. 문제 분해
   • 주어진 점들 중 x, y 각각의 최솟값과 최댓값을 찾는다.
   • (최댓값 x - 최솟값 x) * (최댓값 y - 최솟값 y) = 최소 직사각형 넓이
2. 핵심 로직 흐름

   minX, minY = +INF
   maxX, maxY = -INF

   for each (x, y):
       minX = min(minX, x)
       maxX = max(maxX, x)
       minY = min(minY, y)
       maxY = max(maxY, y)

   넓이 = (maxX - minX) * (maxY - minY)

3. 예외 처리
   • N = 1일 경우 → 점 하나만 존재하므로 넓이는 0

---

코드

1. 최초 작성 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        if(n==1){
            System.out.println(0);
        } else {
            int[][] arr = new int[2][2];
            String[] line;
            for(int i=0;i<n;i++){
                line = br.readLine().split(" ");
                int x = Integer.valueOf(line[0]);
                int y = Integer.valueOf(line[1]);
                if(i==0){
                    arr[0][0]=x;
                    arr[0][1]=y;
                    arr[1][0]=x;
                    arr[1][1]=y;
                } else {
                    if(x<arr[0][0]){
                        arr[0][0]=x;
                    }
                    if(x>arr[1][0]){
                        arr[1][0]=x;
                    }
                    if(y<arr[0][1]){
                        arr[0][1]=y;
                    }
                    if(y>arr[1][1]){
                        arr[1][1]=y;
                    }
                }
            }
            System.out.println((arr[1][0] - arr[0][0])*(arr[1][1] - arr[0][1]));

        }
        
    }
}

2. 개선된 코드 (동일 로직, 가독성 향상)

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        if (n == 1) {
            System.out.println(0);
            return;
        }

        int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;

        while (n-- > 0) {
            String[] line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);

            minX = Math.min(minX, x);
            maxX = Math.max(maxX, x);
            minY = Math.min(minY, y);
            maxY = Math.max(maxY, y);
        }

        System.out.println((maxX - minX) * (maxY - minY));
    }
}

---

시간·공간 복잡도

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)

---

어려웠던 점

• 처음 작성한 코드에서 배열을 통해 최소/최대값을 관리하다 보니 코드 가독성이 다소 떨어졌다.

---

배운 점 및 팁

• 범위 추적 문제에서는 minX, maxX와 같은 변수로 개별 추적하는 것이 코드 명확성 면에서 더 효율적이다.
• 입력 개수가 1개일 때는 넓이가 0임을 별도로 처리해야 한다.

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/9063
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형:

  • [11651] 좌표 정렬하기 2
  • [2583] 영역 구하기

• 확장 문제:

  • 회전한 직사각형 또는 원형 경계의 넓이 계산 문제
  • Convex Hull(볼록 껍질) 기반의 외곽 넓이 계산 문제