[Programmers] #86491 - 최소직사각형 [Java][C++][Python]
[Programmers] #86491 - 최소직사각형 [Java][C++][Python]
1. 아이디어
모든 명함을 수납할 수 있는 가장 작은 지갑의 크기(가로와 세로의 곱)를 구하는 문제로, 명함은 돌려서 수납할 수 있어 가로와 세로의 구분이 의미가 없으므로 명함과 지갑을 모두 긴 변과 짧은 변으로 나누어 본다. 돌려서 들어가려면 명함의 긴 변이 지갑의 짧은 변 이하여야 하는데, 그러면 명함의 두 변이 모두 지갑의 짧은 변 이하여서 어느 방향으로 놓아도 들어가므로 돌려서 들어가는 명함은 돌리지 않고도 들어간다.
따라서 모든 명함이 들어갈 조건은 지갑의 긴 변이 명함들의 긴 변 중 최댓값 이상이고 지갑의 짧은 변이 명함들의 짧은 변 중 최댓값 이상인 것이며, 둘 다 딱 그 값으로 잡은 지갑이 가장 작으므로 답은 두 최댓값의 곱이다.
2. 코드
풀이 [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int solution(int[][] sizes) {
for (int[] x : sizes) {
if (x[0] < x[1]) {
int tmp = x[0];
x[0] = x[1];
x[1] = tmp;
}
}
int w = 0, h = 0;
for (int[] x : sizes) {
w = Math.max(w, x[0]);
h = Math.max(h, x[1]);
}
return w * h;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int solution(vector<vector<int>> sizes) {
for (auto& x : sizes) {
if (x[0] < x[1]) swap(x[0], x[1]);
}
int w = 0, h = 0;
for (auto& x : sizes) {
w = max(w, x[0]);
h = max(h, x[1]);
}
return w * h;
}
1
2
3
4
def solution(sizes):
w = max(max(a, b) for a, b in sizes)
h = max(min(a, b) for a, b in sizes)
return w * h
This post is licensed under CC BY 4.0 by the author.