프그스_완전탐색_최소직사각형_레벨1 (고득점 kit_다시풀기)

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

---

잘못 접근한듯

메모한 것

브루트포스 문제니까

걍 모든 경우의 수 다 해보면 되는 거 아님?
일단 mim(a,b)를 활용해야 하는데

알고리즘

예를들면
max_w = max(가로)
max_h = max(세로)
기본적으로 wallet = max_w * max_h 해놓고

for i in range(len(sizes)):
    가로[i], 세로[i] = 세로[i], 가로[i]          # 하나씩 기울여준다
    wallet = min(wallet, max(가로)*max(세로))
    가로[i], 세로[i] = 세로[i], 가로[i]          # 브루트포스를 위해 돌려놓자
  

---

올바른 접근법

아이디어 - 이해하자

• 명함들이 가로로 세로로 중구난방하게 있잖아 {ㅡ ㅣ ㅣ ㅡ ㅡ ㅣ ㅡ ㅣ} 이런식으로
• 이걸 세로(or가로)로 통일시켜준다고 생각해
  • A4용지 정리할 때처럼
• 즉, 각 명함의 (가로 vs 세로) -> 더 긴 것을 세로에 몰아줘(= ㅡ를 ㅣ로)
  • 그럼 {ㅣ ㅣ ㅣ ㅣ ㅣ ㅣ} 이렇게 될 거 아냐
  • return max(가로) * max(세로)하면 끝

---

잘못 푼 코드1

def solution(sizes):
    # 가로 세로 분리
    w = [i[0] for i in sizes]
    h = [i[1] for i in sizes]
            
    wallet = max(w) * max(h)
    leng = len(sizes)
    for i in range(leng):        
        w[i], h[i] = h[i], w[i]   # swap
        wallet = min(wallet, max(w) * max(h))
        w[i], h[i] = h[i], w[i]
    
    return wallet
    
print(solution([[60, 50], [30, 70], [60, 30], [80, 40]]))
print(solution([[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]))
print(solution([[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]))

잘못 푼 코드2

def solution(sizes):
    # 가로 세로 분리
    w = [i[0] for i in sizes]
    h = [i[1] for i in sizes]
       
    leng = len(sizes)
    wallet = 0
    for i in range(leng):         # i가 기준점
        for j in range(leng):     # j가 모든경우
            if (w[j] <= w[i] and h[j] <= h[i]):   # 현상태
                wallet = max(wallet, w[j] * h[j])
            if (h[j] <= w[i] and w[j] <= h[i]):   # 스왑상태
                wallet = max(wallet, w[j] * h[j])
    
    return wallet
    
print(solution([[60, 50], [30, 70], [60, 30], [80, 40]]))
print(solution([[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]))
print(solution([[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]))

---

솔루션 코드 - 블로그

def solution(sizes):
    w = []
    h = []
    for i in range(len(sizes)):
        if sizes[i][0] >= sizes[i][1]:
            w.append(sizes[i][0])
            h.append(sizes[i][1])
        else:
            h.append(sizes[i][0])
            w.append(sizes[i][1])

    print(w)
    print(h)
    return max(w) * max(h)

print(solution([[60, 50], [30, 70], [60, 30], [80, 40]]))
print(solution([[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]))
print(solution([[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]))