프로그래머스 - 최소직사각형(Java)

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

프로그래머스

 

 

처음에는 제귀알고리즘을 사용해서 가로 새로가 바뀐 모든 경우의 수에서 넓이의 최소값을 구하려고 했는데 너무 복잡해졌다.

 

이 문제를 풀면서 너무 알고리즘의 틀에만 박혀서 문제를 풀면 더욱 어려워질 수 도 있다는 것을 알게 되었다.

 

지금까지 문제를 보면 어떤 알고리즘을 적용 할지부터 생각하는 나 자신을 반성하게 되었다.

 

정해진 알고리즘을 적용하는것이 아닌 사고방식만 틀어서 적용하면 더욱 쉽게 풀 수 있는 문제가 있는데 이게 바로 그 문제이다.

 

 

문제 해결

 

문제는 모든 명함을 넣을 수 있는 지갑의 최소 넓이를 구하면 된다.

 

가로의 최대값 * 세로의 최대값으로 하면 모든 명함을 지갑에 넣을 수는 있지만 넓이가 최소값이 아니다.

 

따라서 이런 방법을 적용 해야한다.

더 넓은 쪽으로 눕히기.....

더 넓은 쪽으로 눕히면

 

만약 가로가 세로보다 크면 ==> 그대로 두기

만약 세로가 가로보다 크면 ==> 눕혀서 가로 세로변경

 

import java.util.*;    
class Solution {
    public int solution(int[][] sizes) {
        int answer = 0;
        int max_h = 0;
        int max_v = 0;
        
        for(int i=0; i<sizes.length; i++){
            int h = Math.min(sizes[i][0],sizes[i][1]);
            int v = Math.max(sizes[i][0],sizes[i][1]);
            
             max_h = Math.max(h,max_h);
             max_v = Math.max(v,max_v);
        }
        answer= max_h*max_v;
        return answer;
    }
 
}

 

 

---

2025년 03월 18일 풀이

import java.util.*;
    
class Solution {
    public int solution(int[][] sizes) {
        int[] width = new int[sizes.length];
        int[] height = new int[sizes.length];
        
        for(int i=0; i<sizes.length; i++){
            int x = sizes[i][0];
            int y = sizes[i][1];
            if(x>y){
                width[i]=x;
                height[i]=y;
            }
            else{
                width[i]=y;
                height[i]=x;
            }
        }
        Arrays.sort(width);
        Arrays.sort(height);
        
        return width[width.length-1] * height[height.length-1];
    }
}