[프로그래머스] 최소직사각형 (시뮬레이션)

문제 소개

오늘 풀었던 최소 직사각형 - 프로그래머스 문제를 정리합니다.
이 문제는 모든 명함을 수납할 수 있는 최소 크기의 지갑을 만들기 위한 시뮬레이션 문제입니다.
핵심은 명함을 회전시켜 수납 가능하다는 점을 고려해, 가로·세로를 정렬하여 최소 면적을 구하는 것입니다.

문제 링크: 최소 직사각형 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 명함을 회전 가능하므로, 항상 더 긴 쪽을 가로로 설정
2. 가로 길이 중 최댓값, 세로 길이 중 최댓값을 추출
3. 이 두 최댓값의 곱이 지갑의 최소 크기

---

해결 과정 및 코드

핵심 아이디어

1. 각 명함에 대해 가로 = max(w, h), 세로 = min(w, h)로 정렬
2. 이렇게 정렬된 명함들 중 가로/세로 각각의 최대값을 구함
3. 해당 최대값들을 곱하면 가장 작은 지갑 크기 계산 가능

코드

시간 복잡도 : O(N)

public class Solution {
    public int solution(int[][] sizes) {
        int maxWidth = 0;
        int maxHeight = 0;

        for (int[] size : sizes) {
            // 가로와 세로 중 더 큰 값을 가로로, 작은 값을 세로로
            int width = Math.max(size[0], size[1]);
            int height = Math.min(size[0], size[1]);

            maxWidth = Math.max(maxWidth, width);
            maxHeight = Math.max(maxHeight, height);
        }

        return maxWidth * maxHeight;
    }
}