[LV1] 최소직사각형- Python

[LV1] 최소직사각형-

---

문제 설명

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

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

가장 긴 가로 길이와 세로 길이가 각각 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 이하인 자연수입니다.

---

입출력 예#1

문제 예시와 같습니다.

---

입출력 예#2

명함들을 적절히 회전시켜 겹쳤을 때, 3번째 명함(가로: 8, 세로: 15)이 다른 모든 명함보다 크기가 큽니다. 따라서 지갑의 크기는 3번째 명함의 크기와 같으며, 120(=8 x 15)을 return 합니다.

---

입출력 예#3

명함들을 적절히 회전시켜 겹쳤을 때, 모든 명함을 포함하는 가장 작은 지갑의 크기는 133(=19 x 7)입니다.

---

입출력 예시

---

풀이 및 코드 리뷰

내가 제출한 답1  (오답)

def solution(sizes):
    answer = []
    for i in range(len(sizes)):
        for j in range(len(sizes[i])):
            answer.append(sizes[i][j])
    result = sorted(answer)
    mid = len(result) // 2
    print(result)
    return max(result) * result[mid-1]

• 처음 문제 풀이를 생각했을때 sizes를 이중 반복문을 사용하여 각각의 값으로 바꿔서 정렬후 반 나누었다.
• 그다음 max를 이용하여 가장 큰값과 리스트의 반으로 나눴을때 첫번쨰 에서 가장 큰거를 곱하면 된다고 생각하고 문제를 풀었다.
• 그러나 명함의 가로와 세로에서 각각 큰값과 작은값을 나눴으면 모를까 전부 리스트로 만들고 거기서 값을 나누니
• 가로와 세로의 구분이 없어지니 가로의 제일 작은값이 세로에 들어가는 등의 구분이 되지 않아 오답이 되버렸다.

내가 제출한 답2  (정답)

def solution(sizes):
    answer = []
    width = 0
    height = 0
    for i in range(len(sizes)):
        answer.append(sizes[i].sort())
    
    for i in range(len(sizes)):
        if width < sizes[i][0]:
            width = sizes[i][0]
    
    for i in range(len(sizes)):
        if height < sizes[i][1]:
            height = sizes[i][1]
    return width * height

• 그다음 생각하고 참고하여 나온것이 다음과 같이 세로와 가로 구분없이 일단 개별적으로 리스트를 정렬시키고
• 그냥 리스트에 처음을 가로 리스트의 두번쨰를 세로로 정하고 각각의 값 중 가장 큰값들을 곱하여 답을 냈다. 

---

다른 사람의 풀이1 (반복문 사용)

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

• 각 sizes의 리스트에서 최솟값과 최댓값을 뽑아 그중 가장 큰값을 곱하였다... 
• min()과 max()를 병합하여 사용하는것도 알게되었다. 

---

총 리뷰

시간복잡도때문이라도 이중 반복문과 같은 "시간 초과"가 나올만한 코딩은 한 번 더 생각하고 코딩을 작성하자,

따로따로 결괏값을 내거나 사용자 지정 함수를 사용하여 결괏값을 가져오는 방법도 있다.