[프로그래머스] 최소직사각형 (자바)

프로그래머스: 최소직사각형

문제 설명

다양한 크기의 명함을 담을 수 있는 최소 직사각형의 크기를 구하는 문제입니다. 주어진 명함의 크기를 담을 수 있는 가장 작은 직사각형의 크기를 구해야 합니다. 명함을 회전시켜서 수납할 수 있기 때문에 각 명함의 가로와 세로 중 더 큰 값을 직사각형의 가로, 작은 값을 세로로 배치합니다.

문제 접근 방법

1. 각 명함의 가로와 세로 크기를 비교합니다.
2. 두 값 중 큰 값을 가로, 작은 값을 세로로 선택하여 최댓값을 갱신합니다.
3. 모든 명함을 확인한 후, 최종적으로 선택된 가로와 세로의 최댓값을 곱하여 최소 직사각형의 크기를 구합니다.

시간 복잡도 분석

O(N)

이 문제는 명함의 개수 N에 대해 각 명함의 가로와 세로 크기를 한 번씩 비교하는 단순한 반복문을 사용합니다. 따라서 시간 복잡도는 O(N)입니다.

해결 방법

아래는 주어진 명함 크기를 바탕으로 최소 직사각형의 크기를 계산하는 Java 코드입니다:

package re_02;

public class PGS_최소직사각형 {

    public static void main(String[] args) {
        int[][] sizes = {
                {60, 50},
                {30, 70},
                {60, 30},
                {80, 40}
        };

        System.out.println(solution(sizes));
    }

    private static int solution(int[][] sizes) {
        int maxW = 0;
        int maxY = 0;

        for (int i = 0; i < sizes.length; i++) {
            int w = sizes[i][0];
            int h = sizes[i][1];

            if (w >= h) {
                maxW = Math.max(maxW, w);
                maxY = Math.max(maxY, h);
            } else {
                maxW = Math.max(maxW, h);
                maxY = Math.max(maxY, w);
            }
        }
        return maxW * maxY;
    }
}