[Java] 프로그래머스 - 최소 직사각형

다시 시작된 알고리즘...완탐부터 차근히 가봅니다~

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

프로그래머스

처음 생각한 풀이

1. 미리 지갑 경우의 수를 다 만들어두고

2. 가장 작은 것부터 명함을 올려서 확인하는데

3. 중간에 하나라도 크면 return 하고 다 작으면 그 지갑의 크기를 return 하려고 했다.

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int[][] sizes) {
        int answer = 0;
        int minSize = Integer.MAX_VALUE;
        
        // 미리 지갑 경우의 수를 다 만들어둔다. (list로)
        int n = sizes.length; // 명함 개수 
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<sizes.length;i++) {
            
        }
        
        Collections.sort(list); // 오름차순 정렬 
        
        // 가장 작은 것 부터 올리면서 명함을 확인하는데 
        for(int i=0;i<list.size;i++) {
            // 확인할 때 뒤집힌 경우까지 같이 확인해서 
            int mul1 = sizes[i][0] * sizes[i][1]; 
            int mul2 = sizes[i][1] * sizes[i][0];
            
            // 중간에 하나라도 크면 그냥 return 종료 
            if(mul1<list.get(i)) return;
            if(mul2<list.get(i)) return;
            
            // 근데 모든 경우가 다 지갑의 경우보다 같거나 작으면 그때 그 지갑의 크기를 return 
            answer = 
        }
        
        return answer;
    }
}

 

근데 이렇게 풀면 시간복잡도가 터진다...배열의 길이가 10000이라는데 저렇게 계속 돌면 시간복잡도가 재밌다 히 이렇게 풀면 코드 길이 쓰레기 된다 히히 

 

그래서 아이디어를 생각해야 한다. !! 

가로를 두 변 중에서 긴 부분으로 세로를 두 변 중에서 작은 부분으로 

 

그럼 왜 이렇게 두면 풀리는걸까? 

가로를 두 변 중에 긴 부분으로 하면 모든 명함을 그냥 눕히는 과정이 된다. 

애초에 처음 생각할 때 부터 눕히고 시작하는거다. 가로를 눕히고 시작하면 세로 길이가 가장 큰 걸 찾아서 곱하면 그 값이 만들 수 있는 지갑 크기 중 가장 작은 지갑이 된다! 

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int[][] sizes) {
        int answer = 0;
        
        // 1. 가로를 두 변 중에 긴 부분 
        // 2. 세로를 두 변 중에 작은 부분 
        // 3. 그래서 각각의 max 를 곱하면 가장 최소 
        
        int maxGaro = Integer.MIN_VALUE;
        int maxSero = Integer.MIN_VALUE;
        
        for(int i=0;i<sizes.length;i++) {
            // 가로, 세로 중에 큰 걸 가로에 두고, 작은 걸 세로에 두고 
            if(sizes[i][0]<sizes[i][1]) {
                int tmp = sizes[i][0];
                sizes[i][0] = sizes[i][1];
                sizes[i][1] = tmp;
            }
            maxGaro = Math.max(sizes[i][0], maxGaro);
            maxSero = Math.max(sizes[i][1], maxSero);
        }
        
        answer = maxGaro * maxSero;
        
        return answer;
    }
}