Diagonal 문제 풀이

Digaonal 문제는

위의 그림처럼 직사각형 또는 정사각형의 배열을 대각선으로 왔다 갔다하면서 그 순서에 따라 값을 출력하는 것이다.

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

문제풀이 1

가장 평범하게 생각할 수 있는 풀이방식이다.

대각선으로 x,y의 값이 사각형의 범위를 벗어나면 위치를 바꾸고 기존의 방향과 반대방향으로 위치를 옮기는 것이다.

이때 필요한 것은
1. 대각선의 방향을 결정하기 위한 Boolean
2. 현재 위치를 저장할 x,y
3. answer에 값을 채울 index
4. row,col의 길이가 필요하다.

그렇다면 어떻게 풀 것인가??

index가 row*col의 개수만큼만 진행하도록 한다.

그리고 방향이 true이면 오른쪽 위 대각선방향으로 올리고 false이면 아래 왼쪽 대각선 방향으로 나아간다.

이 때 x가 0보다 크고 y가 col보다 작으면 사각형의 범위내에 있으므로 그대로 나아간다. 만약 이 조건을 벗어나게 되면 사각형의 밖으로 나가게 된다. 그렇다면 다시 위치를 조정할 필요가 있다.

1. 만약 pattern이 true일 경우(오른쪽 위 대각선)

x값을 하나 더해서 위쪽 방향으로 벗어난 값을 x값 최상단 즉 사각형의 범위내에 들어오게한다.
이때 y값은 col보다 작다면 사각혐 범이내에 있는 것이기 때문에 y값은 조정할 필요가 없다.

다만 만약 y값도 col값과 같거나 크다면 y값에도 사각형 범위내에 들어와야하기 때문에 y값을 줄인다. 이 경우에는 x값을 올리고 y값을 줄이게 되면 바로 직전값의 위치와 동일하기 때문에 x값을 한칸 내려서 위치를 다시 조정해준다.

2. 만약 pattern이 false일 경우(아래쪽 왼쪽 대각선)
   x값을 늘리고 y값을 줄인다.

위의 pattern이 true일 경우와 완전히 반대로 진행하면된다. y를 기준으로 똑같이 신행 해보자

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int x = 0;
        int y = 0;
        int index = 0;
        boolean pattern = true;

        int row = mat.length;
        int col = mat[0].length;

        int[] answer = new int[row * col];

        while (index < row * col) {
            if (pattern) {
                while (x>=0 && y<col) {
                    answer[index++] = mat[x][y];
                    x--;
                    y++;           
                }
                x++;
                if (y>=col) {
                    y--;
                    x++;
                }
            } else {
                while (x<row && y>=0) {
                    answer[index++] = mat[x][y];
                    x++;
                    y--;
                } 
                y ++;
                if (x>=row) {
                    x--;
                    y++;
                }
            }
            
            pattern = !pattern;
        }
        
        return answer;
    }   
}

2. 두번째 풀이법

1번 풀이법과 비슷한 flag를 설정하는데 이 flag는 방향도 정해줄 뿐 아니라 대각선의 방향이 시작하는 위치를 정해준다.

위의 그림 예시를 보면
[1,7,9]가 오른쪽 위 대각선으로 나아가는 시작점이고
[2,6]이 아래쪽 왼쪽 대각선으로 나아가는 시작점이다.

두 while문의 방식은 첫번째 풀이법과 방향성이 비슷하다.

단 차이는 처음 대각선으로 나아가는 위치를 설정해주고 범위를 벗어나면 끝내고 다시 반복하는가 아니면 범위를 벗어났을 때 체크하고 위치를 조정해주는가의 차이이다.

i = Math.min(flag, m-1)의 의미를 이해하기 어려울 수 있다.

이것이 바로 위치를 정해주는 부분이다. 만약 flag가 짝수이면 i값의 위치가 flag와 m의 최소값으로 설정되고
홀수이면 j값의 위치가 flag와 n의 최소값으로 이루어진다.

(솔직히 두번째 풀이는 코드를 보니 이해가 되나 생으로 생각할 수 있을지는 잘 모르겟다;;) 근데 속도는 첫번째가 더 빠르다

class Solution {
    int m;
    int n;
    public int[] findDiagonalOrder(int[][] mat) {
        int cnt = 0;
        m = mat.length;
        n = mat[0].length;
        int[] ans = new int[m*n];
        int i=0, j=0;
        int flag = 0;
        while (cnt < m*n){
            if (flag % 2 == 0){
                i = Math.min(flag, m-1);
                j = flag - i;
                while ( i >= 0 && j < n){
                    ans[cnt] = mat[i][j];
                    cnt++;
                    i--;
                    j++;
                }
            }
            else{
                j = Math.min(flag, n-1);
                i = flag - j;
                while ( i < m && j >= 0){
                    ans[cnt] = mat[i][j];
                    cnt++;
                    i++;
                    j--;
                }
            }
            flag++;
        }
        return ans;
    }
}