[LV.3] 완전탐색 > 최소직사각형

문제

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

프로그래머스

---

문제 설명

• 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어짐
  모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 반환
• 제한사항)
  sizes의 길이는 1 이상 10,000 이하
  sizes의 원소는 [w, h] 형식
  w는 명함의 가로 길이, h는 명함의 세로 길이
  w와 h는 1 이상 1,000 이하인 자연수

---

명함은 회전이 가능하므로, 각 명함마다 가로와 세로를 자유롭게 바꿀 수 있음

→ 명함의 두 변 중 더 긴 변은 항상 가로(w), 짧은 변은 세로(h)로 정렬

예를 들어, [30, 70]은 [70, 30]으로 바꾸어 [w, h] = [70, 30]으로 만들기

---

정답 코드

def solution(sizes):
    max_w = 0
    max_h = 0
    for w, h in sizes:
        w, h = max(w, h), min(w, h)
        max_w = max(max_w, w)
        max_h = max(max_h, h)
    return max_w * max_h

---

코드 설명

def solution(sizes):

• sizes: 명함의 가로와 세로가 담긴 리스트
  예: [[60, 50], [30, 70], [60, 30], [80, 40]]

    max_w = 0
    max_h = 0

• 지갑의 최대 가로길이와 최대 세로길이를 저장할 변수
• 초기값은 0으로 시작

    for w, h in sizes:

• 명함 리스트에서 각 명함의 가로(w), 세로(h)를 하나씩 꺼내기

        w, h = max(w, h), min(w, h)

• 명함은 회전이 가능하므로, 가로와 세로 중 큰 쪽을 항상 가로(w)로 보기
• 즉, 명함을 돌려서라도 항상 큰 쪽이 가로, 작은 쪽이 세로가 되게 하기
   예: [30, 70] → 회전 → w=70, h=30

        max_w = max(max_w, w)
        max_h = max(max_h, h)

 

• 현재 명함의 가로/세로와 이전까지의 최대값을 비교해서 갱신

    return max_w * max_h

• 최종적으로 지갑의 크기(넓이)를 계산해서 반환