[프로그래머스] 최소직사각형

프로그래머스 Lv.1 🌱
최소직사각형
파이썬으로 풀어보기

문제 설명

명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.

예를 들어, 각 명함의 가로와 세로 길이는 다음과 같이 저장되어 있습니다.

[[60, 50], [30, 70], [60, 30], [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 이하인 자연수입니다.

더 자세한 문제 설명과 입출력 예시는 문제 사이트에서 확인해주세요!

내가 작성한 코드

def solution(sizes):
    longest = max(sizes[0]) # 모든 명함 중 가장 긴 길이
    short_long = min(sizes[0]) # 짧은 길이 중에 가장 긴 길이
    
    for size in sizes:
        longest = max(longest, max(size))
        short_long = max(short_long, min(size))
        
    return longest * short_long

(문제 사이트에서 3가지 입출력 예시를 보고 오면 더 이해가 쉽다.)

가장 작은 명함 지갑을 만들고 싶어도 어쨌든 모든 명함 중 가장 긴 부분을 커버할 수 있어야 한다. 그래서 sizes의 모든 길이 중 가장 긴 길이를 찾아 longest 변수에 저장한다.

명함 지갑의 가로 또는 세로는 가장 긴 길이를 기준으로 제작되므로 그 어떤 명함도 가로로 눞히든 세로로 세우든 명함의 가장 긴 부분을 커버할 수 있다.

그렇다면 그 다음은 각 명함의 짧은 길이들 중에 가장 긴 길이로 명함 지갑을 만들어야 한다. 그래야 명함을 회전시켜도 길이가 모자란 부분이 없을 것이다. 따라서 각 명함의 짧은 길이들 중 가장 긴 길이를 short_long 변수에 저장한다.