최소직사각형

문제설명

 

 

 

제한사항

• sizes의 길이는 1 이상 10,000 이하입니다.
  • sizes의 원소는 [w, h] 형식입니다.
  • w는 명함의 가로길이를 나타냅니다.
  • h는 명함의 세로 길이를 나타냅니다.
  • w와 h는 1 이상 1,000 이하인 자연수입니다.

 

 

입출력 예 

 

 

입출력 예 설명

입출력 예 #1
문제 예시와 같습니다.

입출력 예 #2
명함들을 적절히 회전시켜 겹쳤을 때, 3번째 명함(가로: 8, 세로: 15)이 다른 모든 명함보다 크기가 큽니다. 따라서 지갑의 크기는 3번째 명함의 크기와 같으며, 120(=8 x 15)을 return 합니다.

입출력 예 #3
명함들을 적절히 회전시켜 겹쳤을 때, 모든 명함을 포함하는 가장 작은 지갑의 크기는 133(=19 x 7)입니다.

 

 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> sizes) {
    int maxWidth=0,maxHeight=0;
    for(int i=0; i<sizes.size(); i++)
    {
      sort(sizes[i].begin(), sizes[i].end());
      if(sizes[i][0] >= maxWidth)//최대가로길이보다 크면
      {
          maxWidth = sizes[i][0];
      }
      if(sizes[i][1] >= maxHeight)//최대세로길이보다 크면
      {
          maxHeight = sizes[i][1];
      }
    }
    int answer = maxWidth * maxHeight;
    return answer;
}

---

=> (가로, 세로)가 들어있는 배열을 크기 순으로 정렬합니다. 

 

=> algorithm 헤더에 있는 sort함수를 사용하였습니다. 

 

=> 정렬한 이후에 가로중 가장 긴 길이와 세로 중 가장 긴 길이를 추출해냅니다. 

=> 가장 긴 가로 길이 (maxWidth)와 가장 긴 세로(maxHeight)를 곱하여 answer를 반환합니다.