28. 최소직사각형 ★

유형 : 구현

풀이시간 : 40분....

왜 1점짜리일까? 

 

1. 처음 작성한 코드. 그리디로 접근 

def solution(sizes):
    answer = 0
    garo = [sizes[i][0] for i in range(len(sizes))]
    sero = [sizes[i][1] for i in range(len(sizes))]
    maxgaro = max(garo)
    maxsero = max(sero)
    
    #가로 값 바꾸기
    newgaro = garo.copy()
    newsero = sero.copy()
    newgaro[garo.index(maxgaro)] = sero[garo.index(maxgaro)]
    newsero[garo.index(maxgaro)] = maxgaro 
    newgmax = max(newgaro)
    newsmax = max(newsero)
    
    #세로 값 바꾸기
    newgaro2 = garo.copy()
    newsero2 = sero.copy()
    newsero2[sero.index(maxsero)] = garo[newsero2.index(maxsero)]
    newgaro2[sero.index(maxsero)] = maxsero
    newgmax2 = max(newgaro2)
    newsmax2 = max(newsero2)
    
    return min(maxsero*maxsero, newgmax*newsmax, newgmax2*newsmax2)

 

그러나 특정한 case만 detect 가능한 코드였다. 

아예 다르게 구현해 보자 .

 

2. 넓이 활용하기 

def solution(sizes):
    answer = 0
    area = [[sizes[i][0]*sizes[i][1], sizes[i][0], sizes[i][1]] for i in range(len(sizes))]
    area.sort(reverse = True)
    [maxarea, maxwidth, maxdepth] = area[0]
    for paper in area:
        [currarea, currwidth1, currdepth1] = paper
        [currarea, currdepth2, currwidth2] = paper
        if currwidth1 <= maxwidth and currdepth1 <= maxdepth:
            if currwidth2 <= maxwidth and currdepth2 <= maxdepth:
                continue
        else:
            if currwidth2 <= maxwidth and currdepth2 <= maxdepth:
                continue
            else:
                maxwidth1 = max(maxwidth, currwidth1)
                maxdepth1 = max(maxdepth, currdepth1)
                maxarea1 = maxwidth1 * maxdepth1
                maxwidth2 = max(maxwidth, currwidth2)
                maxdepth2 = max(maxdepth, currdepth2)
                maxarea2 = maxwidth2 * maxdepth2
                if maxarea1 < maxarea2:
                    maxwidth = maxwidth1
                    maxdepth = maxdepth1
                    maxarea = maxarea1
                else:
                    maxwidth = maxwidth2
                    maxdepth = maxdepth2
                    maxarea = maxarea2
    return maxarea

 

우선 넓이순 가로 세로 리스트를 만들고 넓이순을 기준으로 정렬한다.

초기 최대 넓이와 가로 세로 길이를 저장하고 for문으로 하나하나 순회하면서, 

명함을 수납하는 두 경우(기본, 돌리는 경우) 계산 -> 

  1) 둘 중 하나라도 기존 max size 사각형 안에 들어가는 경우 : continue (수납 가능)

  2) 둘 다 안되는 경우,즉 수납 불가능한 경우

   1. 둘 모두 계산

   2. 값을 비교해 작은 값으로 max data update 

 

원리는 간단한데 구현에서 계속 실수해서 헤매었다...

구현할 알고리즘을 잘 정리해 두어야 할 것 같다.  

 

 

<모범답안>

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

 

...

역시,, 헛수고를 하고 있었던 거였다. 

x중에서 max인 것(긴 쪽의 길이)의 max와 

x중에서 min인 것(짧은 쪽의 길이)의 max를 곱하면 끝.

ㅎㅎ........