1424. Diagonal Traverse II (대각선 트래버스 II)

2D 정수 배열 nums가 주어지면 아래 이미지와 같이 대각선 순서로 nums의 모든 요소를 반환합니다.

 

예시 1:

입력: nums = [[1,2,3],[4,5,6],[7,8,9]]
출력: [1,4,2,7,5,3,8,6,9]

 

예시 2:

입력: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
출력: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

 

 

조건:

• 1 <= nums.length <= 10^5
•  1 <= nums[i].length <= 10^5
•  1 <= sum(nums[i].length) <= 10^5
•  1 <= nums[i][j] <= 10^5

 

정답:

public class Solution {
    public int[] FindDiagonalOrder(IList<IList<int>> nums) {
        List<Tuple<int, int, int>> tuples = new List<Tuple<int, int, int>>();
        List<int> result = new List<int>();

        for (int i = 0; i < nums.Count; i++)
        {
            for (int j = 0; j < nums[i].Count; j++)
            {
                tuples.Add(new Tuple<int, int, int>(i + j, i, nums[i][j]));
            }
        }
        
        tuples = tuples.OrderByDescending(i => i.Item2).ToList();
        tuples = tuples.OrderBy(i => i.Item1).ToList();

        for (int i = 0; i < tuples.Count; i++)
        {
            result.Add(tuples[i].Item3);
        }
        
        return result.ToArray();
    }
}

해설: 대각선은 행과 열이 같은 즉 i + j가 동일한 수이기 때문에 정렬을 할 수 있도록 List<Tuple>의 Item1에 넣어 하나의 대각선 묶음을 만듭니다.

그리고 해당 대각선내에서도 열이 높은 순서대로 List에 추가되기 때문에 Item2에 열 또한 추가합니다.

그 이후 Item2 즉 열의 내림차순으로 정렬하고 대각선의 오름차순으로 정렬하게되면 요구하는대로 정렬이 완료되고 해당 값들만 result에 추가하여 return해줍니다.