1. 오늘의 학습 키워드
- 완전 탐색
2. 문제: 최소 직사각형
문제 설명
명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.
아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.
| 명함 번호 | 가로 길이 | 세로 길이 |
|---|---|---|
| 1 | 60 | 50 |
| 2 | 30 | 70 |
| 3 | 60 | 30 |
| 4 | 80 | 40 |
가장 긴 가로 길이와 세로 길이가 각각 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 이하인 자연수입니다.
입출력 예
| 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 x 15)을 return 합니다.
입출력 예 #3
명함들을 적절히 회전시켜 겹쳤을 때, 모든 명함을 포함하는 가장 작은 지갑의 크기는 133(=19 x 7)입니다.
3. 나의 풀이
접근 방법
sizes에는 여러 개의 명함의 [가로 길이, 세로 길이] 형태의 리스트들로 이루어져있다. 이 문제는 sizes에 있는 모든 명함을 수납할 수 있는 가장 작은 지갑의 크기를 return 하는 문제이다.
우리가 쉽게 접근 할 수 있는 방법은 가장 가로, 세로 모두 포함해서 가장 큰 값, 두번째로 큰 값을 선택한다면 모든 명함을 수납할 지갑의 크기를 구할 수 있다. 하지만 우리는 수납할 수 있는 지갑 중 가장 작은 크기를 구해야 한다.
그래서, 그 다음으로 생각하면, 가로에서 가장 큰 크기, 세로에서 가장 큰 크기를 생각할 수 있다. 하지만 이것도 문제 조건을 만족하지 못한다.
왜냐하면 위 문제에 나와있듯이 명함을 가로로 눕혀 수납한다면 가로나 세로 중 하나의 변이 굳이 가장 클 필요가 없기 때문이다.
아래 첫번째 예시를 살펴보자.
sizes
[[60, 50], [30, 70], [60, 30], [80, 40]]
- 가로의 최대값: 80
- 세로의 최대값: 70
2번째 명함의 세로가 최대값을 가지는데 이것은 가로로 눕혀 수납한다면
[30, 70] → [70,30]이 된다.
다른 명함들도 살펴보면
- [60, 50]
- 이것은 가로의 최대값 크기에 들어간다.
- 세로도 들어간다.
- 뒤집을 필요가 없다. 가로가 더 크기 때문에
- [60,30]
- 가로의 최대값 크기에 들어간다.
- 세로도 들어간다.
- 뒤집을 필요가 없다.
- [80,40]
- 이 가로가 최대값이다. 즉 80보다 작으면 담을 수 없다.
- 세로가 최대값 크기에 들어간다.
- 뒤집을 필요가 없다.
그렇다면 세로의 최대값인 70 대신 다른 값을 선택할 수 있나?
할 수 있다.
앞선 3개의 명함들 중 세로 길이 50을 선택하면 된다. 여기서 규칙? 방법을 찾게 되었다.
즉 우리는 모든 명함을 담을 수 있는 크기 중 가장 작은 크기를 구해야 하므로, 먼저 가장 큰 길이를 먼저 구해야한다.
그 다음, 명함 하나하나의 가로 길이와 세로 길이 중 더 작은 값들을 모아 그 중에서 가장 큰 값을 구한다.
→ 수납할 수 있는 지갑 중 가장 작은 크기를 구해야 하니까, 가장 작은 값들 중 큰 값을 구하는 것임!!
이 두 값을 곱하면 수납할 수 있는 지갑 중 가장 작은 크기를 구할 수 있다.
이제 위 내용을 기반으로 코드를 구현해보자.
구현 1
def solution(sizes):
# w = 가로, h = 세로
return max(max(x) for x in sizes) * max(min(x) for x in sizes)큰 것들 중 가장 큰 값 * 작은 것들 중 가장 큰 값을 가장 짧게 구현한 방법이다.
반복문을 통해 모든 명함의 사이즈를 확인하기 때문에 완전 탐색 기반의 알고리즘이다.
구현2
구현1 방법을 풀어쓴 방법이다.
def solution(sizes):
w = [] # 큰 것들
h = [] # 작은 것들
for i in range(len(sizes)):
if sizes[i][0] >= sizes[i][1]:
w.append(sizes[i][0])
h.append(sizes[i][1])
else:
h.append(sizes[i][0])
w.append(sizes[i][1])
return max(w) * max(h)가로, 세로를 빈 리스트로 초기값을 정하고 큰 것들은 가로에, 작은 것들은 세로에 담는 방식이다.
구현3
리스트 대신 값을 주고 값을 계속 update해 나가는 방식이다.
def solution(sizes):
max_width = max_height = 0 # 가로, 세로 최댓값 초기화
for size in sizes:
width, height = size
max_width = max(max_width, width, height) # 전체 명함 중에서 가장 큰 최대값을 찾는다.
max_height = max(max_height,min(width,height)) # 명함 하나하나의 가로 길이와 세로 길이 중 더 작은 값들을 모아 그 중에서 가장 큰 최대 값을 찾는다.
return max_width * max_height4. 결과
TestCase
최종 결과
5. 결론
어제 문제와 동일한 완전 탐색 기반의 문제로, 반복문을 활용하여 접근하면 풀 수 있는 문제이다.
읽어주셔서 감사합니다!
