[프로그래머스] 최소직사각형

문제 설명
명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.
표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.
가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.
모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

제한사항
sizes의 길이는 1 이상 10,000 이하입니다.
sizes의 원소는 [w, h] 형식입니다.
w는 명함의 가로 길이를 나타냅니다.
h는 명함의 세로 길이를 나타냅니다.
w와 h는 1 이상 1,000 이하인 자연수입니다.

풀이 00

def solution(sizes):
    # 각 2차원 리스트 내 두 번째 값이 첫 번째 값보다 크면 스왑
    for i in range(len(sizes)):
        if sizes[i][1] > sizes[i][0]:
            sizes[i][0], sizes[i][1] = sizes[i][1], sizes[i][0]

    # 첫 번째 값과 두 번째 값의 최대값 계산
    max_width = max([size[0] for size in sizes])  # 첫 번째 값의 최대값
    max_height = max([size[1] for size in sizes])  # 두 번째 값의 최대값

    # 두 최대값 곱하기
    answer = max_width * max_height
    return answer

sizes[i][1] > sizes[i][0] 조건에 따라 각 서브 리스트의 값을 정렬해 [0]에 큰 값이, [1]에 작은 값이 들어가도록 설정하였으며, 이후 첫번째 원소에서의 최대값을 구하고 두번째 원소에서의 최대값을 구하여 곱하도록 하였다.

풀이 01

def solution(sizes):
    # 각 명함에서 항상 큰 값을 가로, 작은 값을 세로로 맞추기
    max_width = 0
    max_height = 0
    
    for w, h in sizes:
        # 큰 값을 가로, 작은 값을 세로로 정렬
        width, height = max(w, h), min(w, h)
        # 최대값 갱신
        max_width = max(max_width, width)
        max_height = max(max_height, height)
    
    # 최적화된 지갑 크기 계산
    return max_width * max_height

위 풀이 00번에서는 직관적으로 문제를 해석해서 풀고자 하였으며 다시 한번 최적화된 접근법을 사용해 보고자 했다.
모든 명함은 [w, h] 형식으로 주어지므로, 각 명함에서 항상 긴 쪽을 가로로, 짧은 쪽을 세로로 맞춰야한다. 이를 통해 매번 스왑하는 작업을 수행하지 않고 비교 연산만으로 최대값을 구할 수 있게 된다.
이후, 전체 명함에서 최대 가로 길이와 최대 세로 길이를 각각 구한 뒤 두 값을 곱하면 최소 지갑 크기를 계산할 수 있다.
시간 복잡도는 O(n)이며, 각 명함에 대해 1회 비교만 수행하므로 매우 효율적이게 된다.