[C++][Programmers][완전탐색] 최소직사각형

[문제]

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

프로그래머스

 

[해결법]

위의 예시에서 가장 작은 지갑의 크기는 80*70=5600 같지만 2번 명함을 눕히면 가로70, 세로30인 사이즈가 되므로 가장 작은 지갑의 크기는 80 * 50이다.

 

즉, 한쪽을 큰 값을 두고 다른 한쪽을 작은 값으로 셋팅한 후, 가로 중에 가장 큰 값과 세로 중에 가장 큰값을 뽑아야 함을 알 수 있다. 

 

1) 2차원 벡터의 frist값(가로) > second(세로)값인 상태에서 비교하도록 하기. 
2) 2차원 벡터의 first값(가로) 중에 가장 큰 값, second(세로)값 중에 가장 큰값 뽑기
3) 두개 곱해서 return.

 

[알아둘 것]

algorithm 라이브러리의 min, max 함수

min(1,2); // 1
max(1,2); // 2

 

[코드]

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> sizes) {
    int widthMax = 0, heightMax = 0;
    
    for(int i = 0; i<sizes.size(); i++){
        if(sizes[i][0] < sizes[i][1]){
            if(widthMax < sizes[i][1]){
                widthMax = sizes[i][1];
            }
            if(heightMax < sizes[i][0]){
                heightMax = sizes[i][0];
            }
        }else{
            if(widthMax < sizes[i][0]){
                widthMax = sizes[i][0];
            }
            if(heightMax < sizes[i][1]){
                heightMax = sizes[i][1];
            }
        }
    }
    
    return widthMax * heightMax;
}

위에 코드를 min, max 함수 이용해서 정리

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> sizes) {
    int widthMax = 0, heightMax = 0;
    
    for(int i = 0; i<sizes.size(); i++){
        widthMax = max(widthMax, max(sizes[i][0], sizes[i][1]));
        heightMax = max(heightMax, min(sizes[i][0], sizes[i][1]));
    }
    
    return widthMax * heightMax;
}

적절한 STL 사용의 중요성...