[LeetCode] 1424. Diagonal Traverse II

https://leetcode.com/problems/diagonal-traverse-ii/description/

Diagonal Traverse II - LeetCode

leetcode - Diagonal Traverse II

문제 유형 : 그리드 배열, 배열

문제 난이도 : Medium

 

문제

Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.

 

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]

2차원 정수 배열 nums가 주어집니다. 사진과 같은 순서대로 요소를 반환하시오.

 

 

풀이

nums[i][j]에 있는 숫자는 i+j번째 순회에 이어진다.

 

배열의 각 요소들을 순차적으로 읽으면서, 각 요소들의 값을 임시 2차원배열의 [i+j]에 추가한다.

이러면 임시 2차원 배열의 각 배열에는 역순으로 데이터가 저장되어 있다.

[1], [2, 4], [3, 5, 7], 등등..

이를 각각 역순으로 바꾸어주고, 최종 1차원배열에 한 줄로 나열하면 정답이다.

 

 

코드

C++

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        int m=nums.size(),n=0;
        
        for(int i=0;i<m;i++){
            if(n<nums[i].size())
                n=nums[i].size();
        }
        vector<vector<int>>temp(m+n);
        vector<int>ans;
        
        
        for(int i=0;i<m;i++){
            for(int j=0;j<nums[i].size();j++){
                temp[i+j].push_back(nums[i][j]);
            }
        }
        
        for(int i=0;i<m+n;i++){
            reverse(temp[i].begin(),temp[i].end());
        }
        
        for(int i=0;i<m+n;i++){
            for(int j=0;j<temp[i].size();j++){
                ans.push_back(temp[i][j]);
            }
        }
        return ans;
    }
};