[프로그래머스] 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
    
    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

---

느낀점

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