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

문제 링크 - https://programmers.co.kr/learn/courses/30/lessons/86491

• 문제 해결
  처음으로 이 문제를 마주했을 때에는 전부 하나씩 돌려서 확인해야 하나..라고
  생각을 하여 시간복잡도를 계산해 보았더니 말도 안되는 숫자가 나와 패턴을 찾기 시작했다.
  먼저 생각한 것은 주어진 가로, 세로 길이 모두 포함하여 제일 긴 길이는
  가로, 세로 어디에 놓아도 제일 긴 쪽이라는 것이다.
  그래서 제일 긴 길이를 가진 명함을 찾아 고정 한 후에 생각해 보았다.
  생각하다보니 우리가 구하는 것은 명함의 넓이의 최소값이었기 때문에
  각 명함마다 가로, 세로 중 긴 부분을 제일 긴 길이를 가진 명함에 대치시킨다면
  나머지 짧은 부분들은 어차피 각 명함에서 짧은 부분이기 때문에
  이 짧은 부분들의 최대값을 구한다면 제일 긴 길이와 곱하면 최소값이 나왔다.
  따라서

1. 가장 긴 길이를 가진 명함을 구하고 고정시킨 후
2. 나머지 명함들을 긴 부분은 가장 긴 길이를 가진 명함에 대치시키고 (회전)
3. 각 명함들 중 짧은 부분들을 모아 최대값을 산출
   
   그런데 생각해보니 가로, 세로라는 기준점이 있었기 때문에 각 명함들은 긴 부분은 가로로 짧은 부분은 세로로 만든다면 1,2는 한꺼번에 해결되었다.
   따라서 이 방법을 사용하여 구현하고 최소값을 구하였다.

class Solution {
    public int solution(int[][] sizes) {
        
        int max_row = 0; //가로의 최대 길이
        int max_col = 0; // 세로의 최대 길이
        
        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;
            }
            if(max_row<sizes[i][0]) max_row = sizes[i][0]; // 최대값
            if(max_col<sizes[i][1]) max_col = sizes[i][1]; // 최대값
        }
        
        return max_col*max_row; //결과
    
    
}}