[프로그래머스] Lv.1 최소 직사각형 (파이썬)

완전 탐색 문제

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

프로그래머스

---

💡 풀이코드 (실패 - 시간초과)

import sys
sys.setrecursionlimit(10000000)

result = sys.maxsize

def solution(sizes):
    
    def dfs(idx, w_max, h_max):
        global result
        
        if idx == len(sizes):
            result = min(result, w_max * h_max)
            return
        
        for i in range(2):
            n_w_max = max(w_max, sizes[idx][i]) # 0, 1
            n_h_max = max(h_max, sizes[idx][1-i]) # 1, 0
            
            if n_w_max * n_h_max < result:
                dfs(idx + 1, n_w_max, n_h_max)
    dfs(0, 0, 0)
    answer = result
        
    return answer

시간 복잡도

시간 복잡도 계산 (카세르트의 곱)

각각의 명함 번호에서 2가지(1. w, h 2. h, w) 의 경우의 수를 만들 수 있고, 이러한 명함 번호를 조합하여 모든 경우의 수를 찾는다.

따라서, 최악의 경우 N = 10,000일 때, 호출 횟수는 O(2**10000)이 되므로 시간 초과가 발생한다.

---

💡 풀이코드 (실패)

def solution(sizes):
    answer = 0
    
    arr = [x for s in sizes for x in s]
    arr.sort(reverse=True)
    answer = arr[0] * arr[len(arr) // 2]
    return answer

 

명함 번호	가로 길이	세로 길이
1	60	50
2	30	70
3	60	30
4	80	70

 

위의 예시에서 4번 명함의 세로 길이에 있는 70이 두번째로 큰 수 이지만, 가로 길이로 바꿀 수가 없다 (80이 더 크므로)

따라서, 이러한 경우로 인해 오답이 발생한다.

 

잘못된 답 : arr = [80, 70, 70, 60, 60, 50, 30, 30] -> 4800

올바른 답 : 가로 = [60, 70, 60, 80] 세로 = [50, 30, 30, 70] -> 5600

---

💡 풀이코드 (성공)

def solution(sizes):
    answer = 0
    
    w_max = max(sizes, key = lambda x: x[0])[0]
    h_max = max(sizes, key = lambda x: x[1])[1]

    if max(w_max, h_max) == w_max: 
        for i in range(len(sizes)):
            if sizes[i][0] < sizes[i][1]:
                sizes[i][1] = sizes[i][0]
        h_max = max(sizes, key = lambda x: x[1])[1]
    else:
        for i in range(len(sizes)):
            if sizes[i][0] > sizes[i][1]:
                sizes[i][0] = sizes[i][1]
        w_max = max(sizes, key = lambda x: x[0])[0]
        
    answer = w_max * h_max
                
        
    return answer

---

느낀점

시간복잡도를 미리 계산하고 문제를 풀자 ..!