프로그래머스 - 최소직사각형 [파이썬]

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

코딩테스트 연습 - 최소직사각형

---

풀이 과정

모든 명함을 담을 수 있는 가장 작은 지갑을 만들어야 하는데 명함은 회전해서 담을 수 있다.

 

4개의 명함이 있다고 하면 1 2 3 4, 12 13 14 23 24 34, 123 124 134 234, 1234 번째 명함을 회전시켜본 뒤 넓이를 구하고 가장 작은 값을 답으로 내는 방법을 떠올려봤지만 sizes의 길이가 10,000까지 들어오므로 이건 너무 시간이 오래 걸린다.

 

명함은 회전해서 담을 수 있으므로 가로, 세로 길이는 중요하지 않다. 긴 쪽의 길이와 짧은 쪽의 길이를 한 곳에 몰아넣은 다음, 긴 쪽의 길이 중에서 가장 큰 값 * 짧은 쪽의 길이 중에서 가장 큰 값을 해주면 답이 도출할 수 있다. 또한 이렇게 풀면 O(N)의 시간복잡도로 문제를 해결할 수 있다.

---

소스 코드

def solution(sizes):
    max_width, max_height = 0, 0
    for a, b in sizes:
        if a > b:
            a, b = b, a
        max_width = max(max_width, a)
        max_height = max(max_height, b)
    answer = max_width * max_height
    return answer