[JavaScript/알고리즘] 최소직사각형

프로그래머스 Lv.1 "최소직사각형" 문제

프로그래머스

 

주어진 여러 사이즈의 명함들의 가로세로 길이를 모두 수납할 수 있는 가장 작은 사이즈의 지갑을 만드는 알고리즘입니다.

위 예시에서 2번 명함을 가로로 눕힌다면 80(가로)*40(세로) 크기의 지갑으로 모든 명함을 수납할 수 있습니다.

 

변명이지만 이 문제는 알고리즘 고득점 kit의 '완전탐색' 으로 분류되어 있었습니다.

function solution(sizes) {
    const ch = [];
    let res = Infinity;
    
    const dfs = (lv) => {
        if (lv === sizes.length) {
           for (let i = 0; i < sizes.length; i++) {
               if (ch[i] === 1) {
                   sizes[i].reverse();
               }
               
               let maxHor = 0;
               let maxVer = 0;
               
               for (let j = 0; j < sizes.length; j++) {
                   if (maxHor < sizes[j][0]) {
                       maxHor = sizes[j][0];
                   }
                   
                   if (maxVer < sizes[j][1]) {
                       maxVer = sizes[j][1];
                   }
               }
               
               if (res > maxHor * maxVer) {
                   res = maxHor * maxVer;
               }
           } 
        } else {
            ch[lv] = 0;
            dfs(lv + 1);
            ch[lv] = 1;
            dfs(lv + 1);
        }
    }
    
    dfs(0);
    
    return res;
}

 

그래서 DFS 알고리즘을 통해 완전탐색을 시도하였고 테스트 케이스에서 time exceed 에러를 마주하게 되었습니다.

상태 트리를 이용하여 부분집합을 만들고, 부분집합에 포함되면 (ch[lv]가 1일 때) 뒤집고 그렇지 않다면 뒤집지 않는 식으로 모든 경우의 수를 확인하였으나...  보다시피 어마무시한 시간 복잡도를 자랑하는 알고리즘이 되어버렸지요.

 

정확히는 O(2^n * n) 의 시간 복잡도를 가집니다.

명함이 3개가 있다면 3개 각각 뒤집는다, 뒤집지 않는다 의 선택지를 가지고 있기에 8개의 경우의 수가 나오고,

거기에 최소/최댓값을 구하기 위해 반복문을 수행하니 거기에 *3을 곱하기 때문이지요.

 

사실 이 문제는 '가로' 에 긴 면을, '세로' 에 짧은 면을 두고 가로, 세로의 최댓값을 각각 구하면 되는 간단한 문제였습니다.

 

function solution(sizes) {
    let maxHor = 0;
    let maxVer = 0;
    
    for (let size of sizes) {
        let hor = 0;
        let ver = 0;
        
        hor = size[0] > size[1] ? size[0] : size[1];
        ver = size[0] > size[1] ? size[1] : size[0];
        
        if (maxHor < hor) {
            maxHor = hor;
        }
        
        if (maxVer < ver) {
            maxVer = ver;
        }
    }
    
    return maxHor * maxVer;
}

 

즉 이렇게 풀면 O(n) 의 시간 복잡도를 가진다는 것이죠...

 

 

 

교훈

알고리즘을 짜기 쉬운 규칙을 찾아보자

알고리즘 문제를 많이 풀어보자 (이 문제는 사실 유명한 문제임)