Lv 0. 직사각형 넓이 구하기.

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

 

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

int solution(vector<vector<int>> dots) {
    int answer = 0;
    vector<int> xv;
    vector<int> yv;
    xv.push_back(dots[0][0]);
    xv.push_back(dots[1][0]);
    xv.push_back(dots[2][0]);
    xv.push_back(dots[3][0]);
    int x=*max_element(xv.begin(),xv.end())-*min_element(xv.begin(),xv.end());
    yv.push_back(dots[0][1]);
    yv.push_back(dots[1][1]);
    yv.push_back(dots[2][1]);
    yv.push_back(dots[3][1]);
    int y=*max_element(yv.begin(),yv.end())-*min_element(yv.begin(),yv.end());
    answer=x*y;
    return answer;
}

위의 코드는 내가 작성한 풀이이고, 위의 풀이의 경우는 모든 점들의 x좌표를 벡터에 넣어서, 해당 벡터에서 가장 큰 값과 가장 작은 값을 구해서, 해당 값들의 차를 통해서 길이를 구하고, 마찬가지로 모든 점들의 y좌표를 벡터에 넣어서, 해당 벡터에서 가장 큰 값과 가장 작은 값을 구해서, 해당 값들의 차를 통해서 길이를 구하고, 구해진 x축 길이와 y축 길이를 곱해서 출력하는 형태로 작성하였다. 

일단 이렇게 풀이를 생각한 이유는, 주어지는 4좌표가 순서가 보장되지 않는 형태로 주어지기 때문에 전체적으로 모든 경우를 판단해야겠다고 생각했고, 판단에 있어서 점이 4개까지만 주어지기 때문에 for문등을 활용하는 형태가 아닌 위와 같은 형태로 작성하였다. 

 

위와 같은 풀이를 제출하고, 다른 사람의 풀이를 보니까, 가장 처음에 좋아요를 가장 많이 받아서 올라와있는 풀이를 보니까 아주 재미있고 쉽게 해결한 풀이가 있어서 첨부해본다. 

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

using namespace std;

int solution(vector<vector<int>> dots)
{
    int answer=0;

    sort(dots.begin(), dots.end());
    answer=(dots[3][0]-dots[0][0])*(dots[3][1]-dots[0][1]);

    return answer;
}

위의 풀이를 보면, 주어지는 dots를 sort를 통해서 정렬을 하는데, 이때에 sort 함수의 경우는, 기본적으로 사용하면 오름차순 정렬이고, 위와 같이 이 문제의 경우는 원소들이 원소가 2개인 배열의 형태인데, 내가 알고 있던 지식으로는 만약 pair에 대한 정렬이면, 가장 먼저 first에 대해서 정렬하고, 그 뒤에 second에 대해서 정렬을 한다. 원소가 배열인 경우도 마찬가지로 보여진다. 그래서 이런 풀이를 사용할 수 있는 것이다. 

이와 관련하여서 지피티에 sort함수의 적용에 대해서 검색해보고 얻은 정보를 첨부해보면, 

`std::sort` 함수는 C++에서 기본적으로 오름차순으로 정렬을 수행하는 함수입니다. 그러나 이차원 벡터인 `dots`를 정렬하려면 조금 더 세밀한 제어가 필요합니다.

일반적으로 `std::sort`는 기본적으로 첫 번째 원소부터 비교하며 정렬합니다. 그래서 이차원 벡터인 경우, 각 벡터(행)를 비교하여 정렬합니다.

다음은 `dots`의 각 행을 기준으로 정렬되는 방식을 설명하는 예제입니다:

```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<vector<int>> dots = {{2, 3}, {1, 5}, {4, 2}, {3, 6}};

    sort(dots.begin(), dots.end());

    for (const auto& row : dots) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}
```

이 코드에서 `sort(dots.begin(), dots.end())`는 `dots` 벡터의 각 행을 첫 번째 원소부터 비교하여 정렬합니다. 결과는 다음과 같습니다:

```
1 5
2 3
3 6
4 2
```

정렬된 벡터는 첫 번째 열을 기준으로 오름차순으로 정렬되어 있습니다.

그러나 때로는 다른 열을 기준으로 정렬하거나 내림차순으로 정렬해야 할 수도 있습니다. 이를 위해 `std::sort` 함수의 세 번째 인수를 사용하여 정렬 방식을 지정할 수 있습니다. 예를 들어, 두 번째 열을 기준으로 내림차순으로 정렬하려면 다음과 같이 할 수 있습니다:

```cpp
sort(dots.begin(), dots.end(), [](const vector<int>& a, const vector<int>& b) {
    return a[1] > b[1];
});
```

위의 코드에서 람다 함수를 사용하여 정렬 조건을 지정하였습니다. 이렇게 하면 두 번째 열을 기준으로 내림차순으로 정렬됩니다.

따라서 `sort` 함수를 사용하여 이차원 벡터를 원하는 열을 기준으로 정렬하거나 다양한 방식으로 정렬할 수 있습니다.

 

위와 같은 정보를 얻을 수 있다. 

결국 sort를 활용해서, x값이 작은 것부터 큰 순으로 정렬, x값이 같다면 y값이 작은 순부터 큰 순으로 정렬을 시행하기 때문에, 

처음에 순서가 보장되지 않던 점들의 경우, 순서가 보장되는 형태로 정렬할 수 있고, 

해당 순서의 경우는

 

2   4

1   3 

 

형태로 놓여지게 될것이고, 이때에 직사각형의 넓이를 구하는데 필요한 점은 1 과 4의 두점만 있으면 축에 평행한 직사각형의 넓이를 구할 수 있으므로, 

answer=(dots[3][0]-dots[0][0])*(dots[3][1]-dots[0][1]);

이와 같은 한 줄로 표현할 수 있는 것이다. 

다음에 이와 같은 문제를 만나면 sort 함수를 잘 활용해서 문제를 풀어보도록 하자.