[C++] 프로그래머스 - 최소직사각형 (Lv.1)

문제 설명

 

생각하기

처음에는 sizes의 크기만큼 돌면서 각각 sizes[i][0]과 sizes[i][1] 의 가장 큰 값을 w, h에 담고,

모든 명함을 다 담을 수 있는지 True, False로 반환하는 bool isOk() 함수를 만들어,

만약 다 담을 수 있다면 다음으로 큰 값을 w, h에 담는 방법을 생각해 보았다.

 

하지만 이렇게 하면 생각할 것이 너무 많아졌다. 

'다음으로 큰 값'을 계속 loop를 돌며 탐색해야 하고 (전체 배열 탐색), 

w, h 중 어떤 변수를 다음으로 큰 값을 담을지를 정해야 한다. (총 3가지 경우의 수가 나옴)

 

그래서 다시 생각해보니, 처음에 sizes[i][0], sizes[i][1] 중에서 sizes[i][0]이 더 크도록 설정해주고 (sizes[i][0]보다 sizes[i][1]이 더 크다면 swap)

w에는 sizes[i][0] 중 가장 큰 값을, h에는 sizes[i][1] 중 가장 큰 값을 저장해

마지막 answer에는 w와 h를 곱한 값을 넣어 리턴하면 된다.

 

코드

#include <string>
#include <vector>
using namespace std;

int solution(vector<vector<int>> sizes) {
    int answer = 0;
    int w=0, h=0;
    for(int i=0; i<sizes.size(); i++){
        if(sizes[i][0] < sizes[i][1]){
            int tmp = sizes[i][0];
            sizes[i][0] = sizes[i][1];
            sizes[i][1] = tmp;
        }
    }
    
    for(int i=0; i<sizes.size(); i++){
        if(w<sizes[i][0])
            w = sizes[i][0];
        if(h<sizes[i][1])
            h = sizes[i][1];
    }
    answer = w*h;
    return answer;
}

 

결과