[LV.1] 최소직사각형

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

입출력 예

sizes	result
[[60, 50], [30, 70], [60, 30], [80, 40]]	4000
[[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]	120
[[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]	133

1번 예시: 가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.

---

풀이 1

회전해서 넣을 수 있으므로, 주어진 가로와 세로 길이는 고정된 것이 아니다.
주어진 각각의 가로와 세로 길이들에서 최대를 뽑아 넓이를 구해야 하므로 2차원 배열에 각 element마다 길이들을 받으면 더 긴 길이를 가로로 설정, 나머지를 세로로 설정한다.
그 후, 가로들에서 최대값을, 세로들에서 최대값을 뽑아 그 넓이를 구하면 된다.

import Foundation

func solution(_ sizes:[[Int]]) -> Int {
    var longer = [Int]()
    var shorter = [Int]()
    
    for size in sizes {
        if size[0] >= size[1] {
            longer.append(size[0])
            shorter.append(size[1])
        } else {
            longer.append(size[1])
            shorter.append(size[0])
        }
    }
    
    return longer.max()! * shorter.max()!  
}

complexity: $O(n^2)$

append: Int type 배열을 매번 사이즈 조정 후, element 추가: $O(n)$
각 element마다 append: $O(n)$

사이즈가 커지는 test case에서는 4ms까지 나오는 경우도 존재

---

풀이 2

2차원 배열의 각 element, 1차원 배열을 볼 때마다 값을 비교한다. 0번째가 1번째보다 작다면 max비교에 [1]을 할당, min비교에 [0]을 할당한다. 이전까지의 max와 min을 비교해서 새로운 max와 min을 구한다.

import Foundation

func solution(_ sizes:[[Int]]) -> Int {
    var maxLength = 0
    var minLength = 0

    for size in sizes {
        if size[0] < size[1] {    
            maxLength = max(maxLength, size[1])
            minLength = max(minLength, size[0])
        }
        else {
            maxLength = max(maxLength, size[0])
            minLength = max(minLength, size[1])
        }
    }
    
    return maxLength * minLength
}

complexity: $O(n)$