[Programmers Lv.1] 최소직사각형

🔗 Link

문제
풀이

📝 Problem Summary

문제를 한두 문장으로 요약합니다.

💡 Idea

명함을 순회하며, 가장 작은 넓이가 되는 가로 세로 길이를 갱신해 가는 완전 탐색 문제이다.

처음에는 직관적으로 코드를 작성했다. 새로운 명함을 추가할 때 확장된 넓이가 작은 방향으로 추가를 해 갔다.

• 첫 번째 방식

  class Solution {
    public int solution(int[][] sizes) {
        int w = 0, h = 0;   
          
        for(int[] size : sizes){
            int w1 = Math.max(w, size[0]);
            int h1 = Math.max(h, size[1]);
            int area1 = w1 * h1;
              
            int w2 = Math.max(w, size[1]);
            int h2 = Math.max(h, size[0]);
            int area2 = w2 * h2;
              
            if(area1 < area2){
                w = w1; h = h1;
            } else {
                w = w2; h = h2;
            }
        }
  
        return w*h;
    }
  }
  

하지만 살짝 관점을 바꿔서, 각 명함들의 긴 쪽 방향과 짧은 쪽 방향을 일치 시켜 준다면 넓이를 비교하지 않고도 가장 작은 넓이의 지갑을 구할 수 있겠다.

• 두 번째 방식

  class Solution {
    public int solution(int[][] sizes) {
        int max_longSide = 0, max_shortSide = 0;   
          
        for(int[] size : sizes){
            int cur_longSide = Math.max(size[0],size[1]);
            int cur_shortSide = Math.min(size[0],size[1]);
              
            max_longSide = Math.max(max_longSide, cur_longSide);
            max_shortSide = Math.max(max_shortSide, cur_shortSide);
        }
  
        return max_longSide*max_shortSide;
    }
  }
  

  🔑 Code

class Solution {
    public int solution(int[][] sizes) {
        int max_longSide = 0, max_shortSide = 0;   
        
        for(int[] size : sizes){
            int cur_longSide = Math.max(size[0],size[1]);
            int cur_shortSide = Math.min(size[0],size[1]);
            
            max_longSide = Math.max(max_longSide, cur_longSide);
            max_shortSide = Math.max(max_shortSide, cur_shortSide);
        }

        return max_longSide*max_shortSide;
    }
}

🗨️ Side Notes