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

문제 설명

여러 명함 사이즈가 주어질 때, 명함을 모두 넣을 수 있는 지갑의 최소 크기를 구하는 문제

 

• 알고리즘 분류 - Brute Force
• 난이도 - Level 1

---

접근 방법 - Brute Force

명함을 돌릴 수 있기에 가로와 세로 중 큰 값이 중요하다.

따라서 가로와 세로 중 큰 값이 뒤로 올 수 있도록 각 배열을 정렬하고, 배열의 왼쪽 값과 오른쪽 값의 각 최댓값을 구해 곱하였다.

---

답안 코드 - Brute Force

정확성: 100, 합계: 100.0 / 100.0

def solution(sizes):
    answer = 0
    
    max_i = 0
    max_j = 0
    for size in sizes:
        size = sorted(size)
        if max_i < size[0]:
            max_i = size[0]
        if max_j < size[1]:
            max_j = size[1]
    
    answer = max_i * max_j
    
    return answer

 

T(N) = 1+1+1+N*(2log2+1+1+1+1+1)+2 = (5+2log2)N+5

로그의 밑이 2라고 가정하면 T(N) = 7N+5

 

프로그래머스 내에서 추천을 가장 많이 받은 코드는 아래와 같다. 실행시간은 평균적으로 내 코드에 비해 2배 정도 빨랐다.

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

 

시간복잡도를 구해보면

T(N) = (N*2+N)*2 + 1= 6N + 1

 

...이게 맞나? 잘 모르겠다.

아무튼 코드 최적화는 경이로우면서도 나한텐 아직 이른 것 같다. 당분간은 문제 푸는 데에만 집중해야지