[프로그래머스] 최소직사각형 다른 풀이

def solution(sizes):
    _sizes = [sorted(s) for s in sizes]
    return max([x[0] for x in _sizes]) * max([x[1] for x in _sizes])

sizes = [(3,6), (5,4), ...]  // 가로, 세로 길이가 무작위로 들어있음.

1. sorted함수를 이용하여 (작은거, 큰거)로 sizes 원소를 정렬한다. 즉 x[0]은 작은 거, x[1]은 큰 거

2. (작은 것들 중 max)*(큰 것들 중 max)의 값을 반환한다.

 

부가설명: 큰 것들 중 가장 큰 것은 가로, 세로 중 하나가 될 수밖에 없고(필수)

             그 외의 나머지 하나는 최대한 작은 것으로 골라야함. => 작은 것들 중 가장 큰 것으로

 

 

 

<힙큐를 이용하는 방법>

import heapq

def solution(sizes):
    mq_w, mq_h = [], []
    for size in sizes:
        w, h = size[0], size[1]
        if w < h: 
        	w, h = h, w
        heapq.heappush(mq_w, -w)
        heapq.heappush(mq_h, -h)
    return mq_w[0] * mq_h[0]

heapq모듈: 이진 트리 기반의 최소 힙 자료구조 제공

     *) 최소 힙: 트리구조를 이용하여 항상 정렬된 상태로 추가&삭제 가능/ 가장 작은 값 얻기 쉬움

     *) 최소 힙에 -를 붙인 값을 넣음으로써 최대 힙 구현가능

참고자료: [파이썬] heapq 모듈 사용법 | Engineering Blog by Dale Seo

 

mq_w: 큰 값 저장/ mq_h: 작은 값 저장

1. sizes에서 원소를 하나씩 빼서 둘 중 큰 값을 mq_w에 넣고, 작은 값을 mq_h에 넣는다. 항상 1이상의 값이 들어가고, 최대값을 구해야하기 때문에 -를 붙여서 넣어줘야한다.

2. 최소 힙에서 가장 작은 값(-를 붙였으니 가장 큰 값)이 0에 저장되므로, mq_w[0]과 mq_h[0]을 곱한 값을 반환한다.(둘 다 -값이라서 양수가 나옴) 

 

 

 

import heapq as hq

def solution(sizes):
    widths, heights = [], []
    for s in sizes:
        hq.heappush(widths, -max(s))
        hq.heappush(heights, -min(s))
    return hq.heappop(widths) * hq.heappop(heights)

widths: 큰 값 저장/ heights: 작은 값 저장

이것도 힙큐를 이용한 방법이다. 조금 더 간결한 방법인 것 같은데 마지막에는 pop보다 [0]인덱스를 사용해주는게 더 좋은 방법일 것 같다.(O(logN) 시간 추가로 걸림, 정렬할 필요 없음)