[PS] 최소직사각형

문제

프로그래머스

모든 직사각형을 담을 수 있는 최소 직사각형의 넓이 구하기

 

풀이

1. 접근 방식

배열 분류를 두 가지로 한다.

[더 큰 수 그룹] vs [더 작은 수 그룹]

 

이렇게 해서 '더 큰 수' 그룹의 최댓값, '더 작은 수' 그룹의 최댓값을 구한다.

그러면 모든 명함을 다 담을 수 있게 된다.

 

더 간단하게 생각하면, 직접 배열 분류를 나누지 않아도 된다.

계속 그 수를 추적하여 곱하기만 하면 정답이 나온다.

 

2. min(), max()

int row = 0;
int col = 0;

 

 

row에는 더 큰 값을 담고, col에는 더 작은 값을 담는다고 해보자.

size[i][0] , sizes[i][1]

 

 

의 값을 비교하여, 더 큰 값을 row, 더 작은 값을 col에 업데이트하면 된다.

min()과 max()를 이용하여 간단하게 구현할 수 있다.

 

코드

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

using namespace std;

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

 

 

회고

처음에는 가로, 세로 값을 계속 업데이트 해나가면서,

명함을 뒤집는 것이 더 이득인 경우의 수를 모두 구해서

최종 정답을 구하려고 했다.

 

근데 아무리 생각해도 비효율적인 것 같아서

정답을 찾아봤는데 이렇게 쉬운 방법이 있었다.

심지어 다 제공되는 라이브러리만 잘 쓰면 됨

 

레벨 1인 이유가 있었다.

문제 접근 방법을 더 확장해보자