Post

[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.