🌈 시작하며

오늘도 알고리즘 문제를 풀었어요.
요새 제 알고리즘에 있어 관심사는 반복문을 어떻게 잘 전개하는지인데요!
최근에 배열을 예외적인 패턴으로 순회하는 데 있어 애를 먹었기 때문입니다 😢

이번 문제도 그런 문제 중 하나였어요! 한 번 살펴볼까요?

📄 본론

일단 이 문제를 살펴볼 때 특이한 점은 대각선이었어요.
일반적으로 배열을 순회할 때는열 순회 -> 행 순회로 전개되는데요.
이러한 상황이 아니니까, 먼저 가설 하나를 떠올려야만 했습니다.

일반적인 반복문으로 쉽게 해결할 수 있는가?

선택 - while문 사용

나중에 다른 분들의 답을 검토할 때는, 이 역시 가능했습니다.
하지만 저의 경우는 좀 더 직관적인 해답을 떠올려야만 했어요.
따라서 제가 선택한 것은 while문이었습니다.

while문을 택함으로써, 좀 더 행 인덱스 와 열 인덱스 접근에 자유도를 높이기 위함이었어요.

여기서 우리는 몇 가지의 패턴을 찾을 수 있어요.

1. 대각선을 일자로 볼 때, (총 대각선의 길이) = (행 길이) + (열 길이) - 1
2. 대각선의 인덱스가 2로 나누어질 경우에는 위로, 아니면 아래로

이를 코드로 표현해볼까요?

    while (i >= 0 && j >= 0 && i < rowLength && j < colLength) {
      result.push(mat[i][j]);
      
      if (nowCnt % 2 === 0) {
        i -= 1;
        j += 1;
      } else {
        i += 1;
        j -= 1;
      }
    }

대각선 전개 패턴 찾기

이 문제의 특이한 점은 지그재그로 되어있다는 점인데요.
이런 대각선 문제를 처음 보는 데다, 지그재그까지 더하니 정말 어지러웠어요.

먼저 그림으로 살펴보죠!

여기서 혹시 패턴이 보이시나요?

저는 이런 패턴을 찾았어요.

1. 만약 위로 올라가는 대각선에서 열 인덱스가 열 길이를 초과하지 않는 경우 - 오른쪽으로 + 1
2. 만약 위로 올라가는 대각선에서 열 인덱스가 열 길이를 초과하는 경우 - 아래쪽으로 + 1
3. 만약 아래로 내려가는 대각선에서 행 인덱스가 행 길이를 초과하지 않는 경우 - 아래쪽으로
4. 만약 아래로 내려가는 대각선에서 행 인덱스가 행 길이를 초과하는 경우 - 오른쪽으로

자, 그러면 이 while문을 벗어나면 해당 패턴에 맞춰 값을 핸들링해주어야겠죠?

    if (nowCnt % 2 === 0) {
      if (j > colLength - 1) {
        i += 2;
        j = colLength - 1;
      } else {
        i = 0;
      }
    } else {
      if (i > rowLength - 1) {
        i -= 1;
        j += 2;
      } else {
        j = 0;
      }
    }

자, 그렇다면 이제 우리는 모든 패턴을 핸들링해줬어요.
전체 코드는 다음과 같습니다.

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
const findDiagonalOrder = (mat) => {
  const result = [];
    
  const rowLength = mat.length;
  const colLength = mat[0].length;

  const diagonalCnt = rowLength + colLength - 1;

  let i = 0;
  let j = 0;

  for (let nowCnt = 0; nowCnt < diagonalCnt; nowCnt += 1) {

    while (i >= 0 && j >= 0 && i < rowLength && j < colLength) {
      result.push(mat[i][j]);
      
      if (nowCnt % 2 === 0) {
        i -= 1;
        j += 1;
      } else {
        i += 1;
        j -= 1;
      }
    }

    if (nowCnt % 2 === 0) {
      if (j > colLength - 1) {
        i += 2;
        j = colLength - 1;
      } else {
        i = 0;
      }
    } else {
      if (i > rowLength - 1) {
        i -= 1;
        j += 2;
      } else {
        j = 0;
      }
    }
  }

  return result;
};

결과를 볼까요?

결과

무난하게 잘 통과했어요!

다른 코드

혹여나 더 좋은 발상이 있을지 궁금해서 leetcode에서 다른 이들의 답들도 참조했어요. 그리고 깊게 생각해보기에 좋은 코드를 찾았어요.

이 코드는 ShashwatBangar 님께서 21년 11월 21일에 올리신 코드입니다!

var findDiagonalOrder = function(mat) {
    let rows = mat.length;
    let cols = mat[0].length;
    let result = new Array(rows + cols - 1).fill(null).map(() => []);

    for(let row = 0; row < rows; row++) {
        for(let col = 0; col < cols; col++) {
            if((row + col) % 2 === 0) result[row + col].unshift(mat[row][col]);
            else result[row + col].push(mat[row][col]);   
        }
    }
    return result.flat();
};

좋은 발상이었어요.
결국 대각선으로 전개한다는 것은 각 대각선의 행 + 열 값이 같다는 패턴이 존재한다는 것을 발견하셨더라구요.

따라서 위에서 제가 했던 대각선의 총합을 반복문으로 순회한 것을, row+col - 1개의 배열로 만든 다음, 대각선의 순서를 고려해서 push를 하던, unshift함으로써 결정을 해주었어요!

다만 flat을 통해 또 시간 복잡도 O(N)을 쓴다는 것과, unshift를 사용한다는 점을 참고하면, 시간복잡도 측면에서는 불리할 수도 있겠군요.

마치며

이 문제를 풀면서 쉬운 문제임에도, 거의 1시간이 걸렸어요.
그럼에도 또 많은 것을 배웠답니다.

1. 결국 while문으로도 반복문을 쓸 수 있다는 유연함을 배웠어요 👋🏻
2. 반대로 패턴을 찾을 수 있다면 for문으로도 충분히 문제를 풀 수 있다는 것도 배웠습니다 🥰

역시 패턴 찾는 건 가장 어려우면서도 즐거워요. 이상!