완전탐색

완전탐색 문제들 중 하나를 풀었는데, 다른 방법이 있어서 기록한다.

이 문제에서 나는 우선 명함 길이를 모두 가로>세로가 되도록 만들어둔 상태에서 가로의 최대값* 세로의 최대값 을 구했는데

[내 풀이]

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

using namespace std;

int solution(vector<vector<int>> sizes) {
    int w = 0;
    int h = 0;

    for(auto& c: sizes)
    {
        if(c[0] < c[1])
            sort(c.begin(),c.end(), greater<>());
        if(c[0] > w)
            w = c[0];
        if(c[1] > h)
            h = c[1];
    }

    return w*h;
}

다른 사람은 굳이 정렬하지 않고,
아예 배열 중 작은 값을 가로로 삼아서, 그 중 가장 큰 값과
배열 중 큰 값을 세로로 삼아서, 그 중 가장 작은 값을 곱해서 풀었다.

[다른사람 풀이]

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

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++)
    {
        w=max(w,min(sizes[i][0],sizes[i][1]));
        h=max(h,max(sizes[i][0],sizes[i][1]));
    }
    answer=w*h;

    return answer;
}

이러면 정렬을 따로 하지 않아도 풀 수 있다. 시간복잡도는 비슷하지만, sort를 굳이 사용한 내 풀이보다는 효율적이라고 볼 수 있다.