1424. Diagonal Traverse II

• 좌측 상단 코너 부터 시작하여 위 & 오른쪽 방향 대각선으로 모든 숫자를 읽어서 돌려주어야 하는 문제이다.

• 문제를 있는 그대로 해석하여 구현할 경우 시간 복잡도가 에 근접할 수 있으며 시간 초과로 실패한다.
• 행렬에 포함된 전체 숫자의 개수는 개 이지만 row, column의 최대 길이도 각각 가 될 수 있으므로 loop를 잘못 작성하면 만큼 시도하게 될 수 있다.
• 첫번째 힌트(같은 대각선에 속한 숫자의 row, column index 합은 같다)를 보고 풀었다.

• 행렬의 각 숫자를 접근하는 index pair의 목록을 만들고 이것을 원하는 순서로 정렬하여 문제를 해결할 수 있다.
• 먼저 행렬의 각 원소를 접근할 수 있는 index pair의 목록을 만든다.
• index pair를 정렬한다.
• 각 대각선에 포함된 원소의 row, column index의 합이 동일하고 합이 작은 대각선 부터 접근해야 한다.
• 따라서 row, column index의 합이 다른 경우 작은 순서대로 정렬한다.
• 만약 row, column index의 합이 같다면 row index가 큰 것이 먼저 오도록 정렬한다.
• 정렬된 index pair 목록을 이용하여 행렬의 각 숫자를 접근하여 돌려준다.

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        vector<pair<int, int>> indices;
        for (int i = 0; i < nums.size(); ++i) {
            int n = nums[i].size();
            for (int j = 0; j < n; ++j) {
                indices.emplace_back(i, j);
            }
        }
        auto compare = [](pair<int, int>& a, pair<int, int>& b) {
            int aSum = a.first + a.second;
            int bSum = b.first + b.second;
            return aSum != bSum? aSum < bSum : a.first > b.first;
        };
        sort(indices.begin(), indices.end(), compare);
        vector<int> result;
        result.reserve(indices.size());
        for (auto& i : indices) {
            result.push_back(nums[i.first][i.second]);
        }
        return result;
    }
};