문제
해결 방안 고민
// 가장 긴 가로 길이, 세로 길이 => 80, 70
// 2번 명함을 가로로 눕힐 경우 80(가로) X 50(세로) 크기의 지갑으로 모든 명함 수납 가능
// 가로로 눕힌다 => 가로가 세로가 될 수도 있다
// 지갑의 크기 => 80 x 50 = 4000 (모든 명함을 수납할 수 있는 가장 작은 지갑)
// 최대 가로 길이, 최대 세로 길이를 통해 각 명함의 가로, 세로를 비교
// 2차원 배열 순회 - 가로를 가로로만 세로를 세로로만 써야한다는 관점에서 벗어나기
// 최소직사각형의 조건: 가로든 세로든 한 쪽의 길이를 최대로 만들면 된다!
Java
복사
•
가로로 눕힌다는 내용을 생각해보면 결국 가로 세로 상관없이 한쪽의 최대 길이를 구하면 된다는 의미이다.
•
그렇기 때문에 한 쪽의 최대 길이를 구하면 나머지 길이는 고려하지 않아도 된다.
해결 방법
•
가장 긴 길이를 가진 명함을 구하고 고정시킨다.
•
나머지 명함들의 최대 길이(가로 or 세로)를 기준 대상의 명함의 가장 긴 길이와 비교한다.
◦
만약에 이전 명함의 길이보다 큰 수가 나오면 해당 수를 최대 길이로 지정한다.
•
min 메소드를 이용하여 각 명함에서 가로와 세로 중 짧은 부분을 확인한다.
코드
package algo250309;
// 최소직사각형 - Lv1
public class Pro86491 {
public int solution(int[][] sizes) {
int maxW = 0;
int maxH = 0;
for (int[] size : sizes) {
int w = Math.max(size[0], size[1]);
int h = Math.min(size[0], size[1]);
maxW = Math.max(maxW, w);
maxH = Math.max(maxH, h);
}
return maxW * maxH;
}
}
Java
복사