Diagonal Traverse (Java)

https://leetcode.com/explore/learn/card/array-and-string/202/introduction-to-2d-array/1167/

Explore - LeetCode

 SSAFY 10기 동기분들과 함께 최소 1일 1블로그를 약속하고, 개발 분야를 바꾸기 위해 Java로 블로그 포스팅을 다시 시작하려고 합니다!!

 해당 문제는 제가 문제 푸는데 소요한 시간에 비하여 놀랍게도 딱 한 줄입니다. 

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

 즉, 2차원 배열의 [0][0] 지점 부터 북동쪽 방향으로 탐색 ->  남서쪽 방향 탐색을 반복하여 2차원 배열의 마지막 지점에 도달합니다. 탐색하는 동안 순서대로 1차원 배열에 값을 저장하여 반환합니다.

이를 그림으로 표현 하면 아래와 같습니다.

탐색 위치에 따라 값을 저장하여 1차원 배열로 반환함에 따라

아래 예시의 Input 2차원 배열은 Output 1차원 배열로 전환됩니다.

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

 

코드 작성 전, 아래와 같이 솔루션 단계를 정리하였습니다.

▶  탐색 반복 횟수 = 2차원 배열의 행 갯수 + 열 갯수 -1번 ( 변수명 nIter )

▶  규칙을 찾기 위해, 모든 방향이 남서쪽 탐색이라고 가정. ( 탐색 시작점이 ㄱ자 방향으로 진행됨)

▶  중간 대각선을 기준으로 북서쪽은 행이 고정, 남동쪽은 열이 고정 ( 행 = nRowPoint, 열 = nColPoint)

▶  본래 북서쪽 탐색인 경우 1차원 배열 변환 시 원소 순서를 반대로 대입.

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int nRows = mat.length;
        int nCols = mat[0].length;
        
        int nRowPoint = 0;
        int nColPoint = 0;
        
        int nIter = nRows + nCols -1;
        
        int nIndex = 0;
        int[] nArrResult = new int[nRows*nCols];
        
        ArrayList<Integer> arrTemp = new ArrayList<>();
        
        for(int i = 0; i < nIter; i++) {
            arrTemp.clear();
            
            if(i < nCols) {
                nRowPoint = 0;
                nColPoint = i;
            }
            else {
                nRowPoint = i+1 - nCols;
                nColPoint = nCols-1;
            }
            
            while (nRowPoint < nRows && nColPoint >= 0) {
                arrTemp.add(mat[nRowPoint][nColPoint]);
                nRowPoint++;
                nColPoint--;
            }
            
            if(i % 2 == 0) {
                for(int j = arrTemp.size()-1; j>= 0; j--)
                    nArrResult[nIndex++] = arrTemp.get(j);
            }
            else {
                for(int j = 0; j < arrTemp.size(); j++)
                    nArrResult[nIndex++] = arrTemp.get(j);
            }
        }
        
        return nArrResult;
    }
}

C++ 쓰다가 Java로 Arraylist 활용하려고 하니 쉽지가 않네요 ㅠㅠ.

긴 글 읽어주셔서 감사합니다!