498 - Diagonal Traverse

정보

• 문제 보기: 498 - Diagonal Traverse
• 소요 시간: 12분 10초
• 풀이 언어: java
• 체감 난이도: 2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

구현 시뮬레이션

풀이 코드

정보

• 메모리: 45770 KB
• 시간: 2 ms

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[] ans = new int[n*m];

        int i = 0, j = 0;
        int cnt = 0;
        boolean up = true; // traversal direction
        
        while (cnt < n*m) {
            ans[cnt] = mat[i][j];
            if (up) {
                if (i == 0 || j == m-1) {
                    up = false; // change to down
                    if (j == m-1) ++i; // no more space to go right -> go down
                    else ++j; // go right
                }
                else {
                    --i;
                    ++j;
                }
            }
            else {
                if (i == n-1 || j == 0) {
                    up = true; // change to up
                    if (i == n-1) ++j; // no more space to go down -> go right
                    else ++i; // go down
                }
                else {
                    ++i;
                    --j;
                }
            }
            ++cnt;
        }

        return ans;
    }
}

풀이 해설

주어진 배열을 대각선 순회하는 문제이다.

m == n 이라는 조건은 없으므로 각 상황에서의 조건을 잘 생각해서 처리해줘야 한다.

전체 코드는 3중 if-else로 구성되고 이를 설명하자면 다음과 같다.

1️⃣ 1중첩: 어느 방향 진행인가?

문제에 제시된 대로 진행은 up / down 둘 중 하나이다.

2중첩의 else 문이 일반적인 up / down 로직이다.

if (up) {
    if (i == 0 || j == m-1) ...
    else {
        --i;
        ++j;
    }
}
else {
    if (i == n-1 || j == 0) ...
    else {
        ++i;
        --j;
    }
}

2️⃣ 2중첩: 현재 경계에 도달했는가?

y축이든 x축이든 일단 경계에 닿았다면 방향을 반대로 틀고, 오프셋을 조정한다.

오프셋은 대충 예시의 3 x 3 그림을 보고 정하면 된다.

if (up) {
    if (i == 0 || j == m-1) {
        up = false; // change to down
        if (j == m-1) ++i; // no more space to go right -> go down
        else ++j; // go right
    }
    else ...
}
else {
    if (i == n-1 || j == 0) {
        up = true; // change to up
        if (i == n-1) ++j; // no more space to go down -> go right
        else ++i; // go down
    }
    else ...
}

3️⃣ 3중첩: 오프셋 조정할 공간이 있는가?

하지만 y축과 x축 중 어느 축의 경계에 닿았는지에 따라 조정할 오프셋이 달라진다.

만약 위로 올라가다가 x축 경계에 닿으면 더이상 우측으로 오프셋을 조정할 수 없으므로 대신 밑으로 내리고,

아래로 내려가다가 y축 경계에 닿으면 더이상 하측으로 오프셋 조정이 불가하므로 대신 우측으로 민다.

if (up) {
    if (i == 0 || j == m-1) {
        up = false; // change to down
        if (j == m-1) ++i; // no more space to go right -> go down
        else ++j; // go right
    }
    else ...
}
else {
    if (i == n-1 || j == 0) {
        up = true; // change to up
        if (i == n-1) ++j; // no more space to go down -> go right
        else ++i; // go down
    }
    else ...
}

메모

• EZ simulation (0.35 삼성)
• 2014 Bloomberg entry level SDE interview 기출