최소직사각형

문제 설명

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

 

가장 긴 가로 길이와 세로 길이가 각각 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. sizes의 요소를 뽑아내어 요소 리스트의 큰 값(가로)과 작은 값(세로)을 찾아낸다.

2. 가로와 세로 중 각각 가장 큰 값을 구한다.

3. 가장 큰 값 끼리 곱하여 지갑의 크기를 반환한다.

 

def solution(sizes):
    size = [0, 0]
    
    for i in sizes:
        min_i, max_i = min(i), max(i)
        
        if size[0] < max_i:
            size[0] = max_i
            
        if size[1] < min_i:
            size[1] = min_i
            
    answer = size[0] * size[1]
    
    return answer
    
    
테스트 10 〉	통과 (0.04ms, 10.2MB)
테스트 11 〉	통과 (0.07ms, 10.2MB)
테스트 12 〉	통과 (0.10ms, 10.3MB)
테스트 13 〉	통과 (0.34ms, 10.3MB)
테스트 14 〉	통과 (0.70ms, 10.4MB)
테스트 15 〉	통과 (0.95ms, 10.4MB)
테스트 16 〉	통과 (1.69ms, 10.6MB)
테스트 17 〉	통과 (2.87ms, 10.9MB)
테스트 18 〉	통과 (2.62ms, 10.9MB)
테스트 19 〉	통과 (2.67ms, 11.4MB)
테스트 20 〉	통과 (3.18ms, 11.4MB)

나는 size 라는 최종 지갑 사이즈 리스트를 만들고 인덱스 0번과 1번에 가로 세로의 길이를 넣을수 있도록 작성했다.

 

 

 

아래는 다른 사람이 푼 코드이다.

 

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


테스트 10 〉	통과 (0.04ms, 10.2MB)
테스트 11 〉	통과 (0.07ms, 10.2MB)
테스트 12 〉	통과 (0.11ms, 10.3MB)
테스트 13 〉	통과 (0.32ms, 10.3MB)
테스트 14 〉	통과 (0.66ms, 10.4MB)
테스트 15 〉	통과 (0.97ms, 10.4MB)
테스트 16 〉	통과 (1.50ms, 10.6MB)
테스트 17 〉	통과 (2.19ms, 10.9MB)
테스트 18 〉	통과 (2.37ms, 10.8MB)
테스트 19 〉	통과 (2.59ms, 11.4MB)
테스트 20 〉	통과 (3.10ms, 11.4MB)

효율성은 유사하지만 코드는 더 간결하다.

 

나같은 경우에는 for 1번, if 2번, min과 max를 총 2번 사용하였고

이 코드는 for 2번, min과 max는 총 4번 사용하였다.

 

 

 

---

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges