[프로그래머스 Level 1] 최소직사각형 (Java)

문제

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

프로그래머스

 

 

실패한 코드 (완전 탐색 nC1+ nC2+ nC3+ ....nCn)

처음에는 시간 복잡도를 생각 안하고 1개의 명함을 뒤짚는 경우, 2개의 명함을 뒤짚는 경우.. 를 생각하면서 모든 경우 의 수를 재귀를 통해 구하려고 했었다. 테스트케이스는 통과했으나 제출시, 역시나 시간 초과였다.

class Solution {
    static int answer=1234567890;
    public int solution(int[][] sizes) {               
        //i개의 명함을 뒤짚는 경우의수 구하기
        for(int i=1; i<=sizes.length; i++){
            pick(0,0,i, sizes);
        }
        return answer;    
    }
    
    public void pick(int idx, int pick, int cnt, int[][] sizes){
        if(pick==cnt){
            int maxWidth= 0;
            int maxHeight= 0;
            //가로 최소 값 구하기
            for(int i=0; i<sizes.length; i++){
                maxWidth=Math.max(sizes[i][0],maxWidth);
            }
            
            //세로 최소 값 구하기
            for(int i=0; i<sizes.length; i++){
                maxHeight=Math.max(sizes[i][1],maxHeight);
            }
            
            answer= Math.min(maxWidth*maxHeight,answer);
            return;
        }
        
        for(int i= idx; i<sizes.length; i++){
        	//가로, 세로 뒤짚기
            int temp= sizes[i][0];
            sizes[i][0]=sizes[i][1];
            sizes[i][1]=temp;        
            pick(i+1,pick+1,cnt,sizes);
            //원래 대로 복원
            temp= sizes[i][0];
            sizes[i][0]=sizes[i][1];
            sizes[i][1]=temp; 
        }
    }
}

 

정답 코드

1. 명함별로 가로/세로 구분 없이 최대값(max), 최소값(min)을 구한다.

2. 해당명함의 최대값(max)이 최종최대값(fmax)와 비교하여 더 큰 값을 fmax에 set한다.

  최소값도 마찬가지로 해당명함의 최소값(min)이 최종최소값(min)과 비교하여 더 큰 값을 fmin에 set한다.

-- 최소값을 set할때도 더 큰 값을 set하는 이유는 궁극적으로 명함이 들어가는 최소직사각형이기 때문!

class Solution {
    public int solution(int[][] sizes) {
        int answer = 0;
        int fmax = 0;
        int fmin = 0;
        for(int i=0; i<sizes.length; i++){
            int max = Math.max(sizes[i][0], sizes[i][1]);
            int min = Math.min(sizes[i][0], sizes[i][1]);
            
            fmax= Math.max(fmax, max);
            fmin= Math.max(fmin, min);
        }
        
        answer = fmax*fmin;
        return answer;
    }
}