[programmers/python] 최소직사각형 - 완전탐색

문제 설명

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

회사는 명함을 수납할 수 있는 지갑을 만들려고 한다. 모든 명함을 돌리거나 눕힐 수 있다는 전제하에, 모든 명함을 한 지갑 안에 넣을 수 있도록 가장 작은 지갑의 크기를 구해야 한다.

예를 들어 다음과 같은 명함 정보가 있다고 하자:

 

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

 

이 명함들을 적절히 눕혀 넣으면, 80(가로) x 50(세로)의 지갑으로 모두 수납할 수 있고, 이는 최소 크기인 4000이 된다.

---

핵심 아이디어

모든 명함은 회전이 가능하므로, 각 명함의 긴 변을 가로로, 짧은 변을 세로로 본다고 해도 무방하다. 즉, 모든 명함의 [가로, 세로]를 sorted()를 통해 [작은 쪽, 큰 쪽]으로 정리한 후:

• 가로 길이의 최댓값 (긴 쪽)
• 세로 길이의 최댓값 (짧은 쪽)

을 곱하면, 모든 명함을 수납할 수 있는 지갑의 최소 크기를 얻을 수 있다.

이처럼 각 명함을 두 가지 방향으로 전환해보는 모든 경우의 수를 탐색하는 방식은 완전탐색(Brute-force)에 해당한다.

---

구현 코드

def solution(sizes):
    # 각 명함을 짧은 쪽, 긴 쪽 순으로 정렬
    sizes_sorted = [sorted(size) for size in sizes]
    
    # 각 방향에서 최대값 찾기
    max_w = max(s[0] for s in sizes_sorted)  # 가로 최댓값 (짧은 쪽)
    max_h = max(s[1] for s in sizes_sorted)  # 세로 최댓값 (긴 쪽)
    
    return max_w * max_h

---

코드 설명

1. sorted(size)로 각 명함을 [작은 쪽, 큰 쪽] 순서로 정리한다.
2. 모든 명함 중 가장 큰 **짧은 변(max_w)**과 가장 큰 **긴 변(max_h)**을 구한다.
3. 그 둘을 곱한 값이 지갑의 최소 크기이다.

이 방식은 완전탐색이라고 볼 수 있는데, 이유는 다음과 같다:

• 각 명함마다 회전 여부를 고려한다 → 경우의 수를 모두 체크
• 단, 정렬을 통해 효율적으로 처리하고 있기 때문에 매우 빠르다 (O(n))

---

예시 분석

solution([[60, 50], [30, 70], [60, 30], [80, 40]])

• 정렬 → [[50, 60], [30, 70], [30, 60], [40, 80]]
• 가로 최댓값: max(50, 30, 30, 40) → 50
• 세로 최댓값: max(60, 70, 60, 80) → 80
• 결과: 50 * 80 = 4000