leet code

1167 - Digonal Traverse

간단한 문제처럼 보였지만, 저는 익숙하지 않은 탓에 쉽게 풀 수 없었습니다.

첫 시도는 간단한 수학 + 예외들은 프로그래밍으로 처리하는 방식으로 생각했습니다.

두 번째 시도는 수학을 사용하지 않고, 단순히 프로그래밍적으로 해결하는 방식입니다.

속도가 488ms => 48ms 로 10배 정도 빨라졌습니다.

C++. 초기버전. time(beats 0%), space(beats 96.80%)

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        int y_size = mat.size();
        int x_size = mat[0].size();
        vector<int> result(x_size*y_size);

        int idx = 0;
        int x=0;
        int y=0;
        for(int i=0; i<y_size+x_size-1; ++i)
        {
            for(int j=0; j<=i; ++j)
            {
                if(i%2 == 0)
                {
                    x = j;
                    y = i-j;
                }else
                {
                    x = i - j;
                    y = j;
                }
                if(x<0) continue;
                if(x>=x_size) continue;
                if(y<0) continue;
                if(y>=y_size) continue;
                result[idx++] = mat[y][x];
            }
        }

        return result;
    }
};

C++. solution. time(beats 40.31%), space(beats 96.80%)

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        int rows = mat.size(), cols = mat.front().size();
        int row = 0, col = 0;
        vector<int> result(rows * cols, 0);
        for (int i = 0; i < result.size(); ++i) {
            result[i] = mat[row][col];
            if ((row + col) % 2 == 0) {
                if (col == cols - 1) {
                    ++row;
                }
                else if (row == 0) {
                    ++col;
                }
                else {
                    --row;
                    ++col;
                }
            }
            else {
                if (row == rows - 1) {
                    ++col;
                }
                else if (col == 0) {
                    ++row;
                }
                else {
                    ++row;
                    --col;
                }
            }
        }
        return result;
    }
};