프로그래머스 (Level 2) - 최소직사각형

1. 문제 설명

• 명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 한다.

명함 번호	가로 길이	세로 길이
1	60	50
2	30	70
3	60	30
4	80	40

• 가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) * 70(세로) 크기의 지갑으로 모두 넣을 수 있다.
• 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) * 50(세로) 크기의 지갑으로 넣을 수 있다.
  • 이때의 지갑 크기는 4000(80*50)이다.
• 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개 변수로 주어진다.
• 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return해라

---

2. 제한사항

• sizes의 길이는 1 이상 10,000 이하이다.
  • sizes의 원소는 [w, h]형식이다.
  • w는 명함의 가로 길이를 나타낸다
  • h는 명함의 세로 길이를 나타낸다.
  • w와 h는 1 이상 1,000 이하인 자연수이다.

3. 입출력 예

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번은 문제 예시와 같다.
• 2번은 3번째 명함(8,15)이 다른 모든 명함보다 크기가 크다. 따라서 지갑의 크기는 3번째 명함의 크기와 같으며 120(8*15)를 return한다.
  • 지갑은 원래대로라면 14 * 15 이지만 [10,7]은 눕혀서 [7,10], [12,3]도 눕혀서 ... 하면 모두 담을 수 있다.

---

4. 풀이 접근

1. 가로나 세로로 눕힐 수 있으므로 각 명함중 가장 긴 변을 가로라고 생각하자.
   1. 모든 명함중에서 가로중 가장 긴 변을 고른다. 
2. 나머지 남은 변을 세로라고 생각하자.
   1. 모든 명함중에서 세로중 가장 긴 변을 고른다.
3. 그러면 모든 명함이 들어갈 수 있는 최적의 직사각형을 만들 수 있다.

---

5. 코드

def solution(sizes):
    return (max(max(i) for i in sizes) * max(min(i) for i in sizes))

• 긴 변중에 가장 긴 것을 골랐고(max)
• 남은 변중에 가장 긴 것을 골랐다.(min)

---