프로그래머스 - 최소직사각형 (JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

 

접근 방식) 완전탐색: 만들 수 있는 모든 명함의 크기 중 제일 큰 걸 찾으면 된다.

명함의 가로 중 제일 긴 거, 세로 중 제일 긴 거를 찾아서 곱하면 된다. 

하지만 주의할 점은 명함을 회전시켜, 가로와 세로를 바꿀 수 있다는 점이다.

그래서, 명함의 긴 부분을 가로, 짧은 부분을 세로로 하기로 정했다.

가로 = 명함의 두 값 중 큰 값세로 = 명함의 두 값 중 작은 값

 

우리에게 주어진 sizes 배열을 돌면서, 이전 가로/세로와 비교하면서 

새로 구한 가로/세로 값이 더 크다면 갱신시켜주면 된다. 

→ 방향을 통일시켰으니, 명함의 가로 중 제일 긴 거, 세로 중 제일 긴 거를 찾아서 곱하면 된다.

 

코드는 매우 간단하다..

class Solution {
    public int solution(int[][] sizes) {
        // 모든 명함을 더 긴 부분이 가로가 되게 포갠다.
        // 다른 명함과 가로, 세로 각각 비교하며 최댓값 구해서 넓이 구한다.
        int width = 0;
        int height = 0;
        for (int i = 0; i < sizes.length; i++) {
            width = Math.max(width, Math.max(sizes[i][0], sizes[i][1]));
            height = Math.max(height, Math.min(sizes[i][0], sizes[i][1]));
        }
        return width * height;
    }
}