Rotate Matrix

[hsskey]

Rotate metrix

N x N 행렬로 표현된 이미지를 90도 회전시키는 메서드를 작성하라. 각 픽셀은 4바이트로 표현되며, 부가적인 행렬을 사용하지 않고 해결해야 한다.

📝 제약조건

• 입력: N x N 2차원 배열 (행렬)
• 부가적인 행렬 사용 금지
• 각 픽셀은 4바이트로 표현됨

💡 예시

• Input: [[1,2,3],[4,5,6],[7,8,9]]
  • Output: [[7,4,1],[8,5,2],[9,6,3]]
• Input: [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
  • Output: [[13,9,5,1],[14,10,6,2],[15,11,7,3],[16,12,8,4]]

문제 해결 과정

Step 1: 문제 이해하기

• 입력: N x N 2차원 배열 (정수)
• 출력: 90도 회전된 N x N 2차원 배열
• 제약조건: 추가 메모리 사용 최소화 (in-place 알고리즘)
• 각 픽셀이 4바이트라는 정보는 알고리즘 구현에 직접적인 영향을 주지 않음

Step 2: 접근 방법

• 직관적으로 생각하기
  • 90도 회전은 행렬의 전치(transpose)와 각 행의 역순으로 구현 가능
  • 추가 메모리 사용을 최소화해야 하므로 in-place 알고리즘 필요
• 자료구조와 알고리즘 활용
  • 2차원 배열 조작
  • 행렬 전치 알고리즘
  • 배열 역순 알고리즘
• 메모리 사용
  • 추가 배열 없이 원본 배열에서 직접 조작 (in-place)

Step 3: 코드 설계

1. 행렬 전치 (transpose)
   • 대각선을 기준으로 원소 교환
2. 각 행 뒤집기
   • 각 행의 첫 번째 원소와 마지막 원소부터 시작해 안쪽으로 이동하며 교환

Step 4: 코드 구현

function rotateMatrix(m) {
  const n = m.length;

  // 1. 전치 (transpose)
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      [m[i][j], m[j][i]] = [m[j][i], m[i][j]];
    }
  }

  // 2. 각 행 뒤집기
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n / 2; j++) {
      [m[i][j], m[i][n-1-j]] = [m[i][n-1-j], m[i][j]];
    }
  }

  return m;
}

// 테스트
console.log(rotateMatrix([[1,2,3],[4,5,6],[7,8,9]]));
console.log(rotateMatrix([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]));

• 시간 복잡도: O(N^2), 여기서 N은 행렬의 한 변의 길이
• 공간 복잡도: O(1), 추가 메모리를 사용하지 않고 in-place로 구현

Step 5: 문제풀이 형상화

1. 전치 (transpose) 과정:

   [1 2 3]    [1 4 7]
   [4 5 6] -> [2 5 8]
   [7 8 9]    [3 6 9]

2. 각 행 뒤집기:

   [1 4 7]    [7 4 1]
   [2 5 8] -> [8 5 2]
   [3 6 9]    [9 6 3]

이 방법을 통해 추가 메모리 사용 없이 효율적으로 행렬을 90도 회전시킬 수 있습니다.

[hsskey]

transposed 처리를 새로운 변수배열로 받아 개선한 풀이

function rotateMatrix(m){
    const rows = m.length
    const cols = m[0].length
    //1. transpose
    const transposed = Array.from({length: cols}, () => new Array(rows));
    for (let i = 0; i < rows; i++) {
      for (let j = 0; j < cols; j++) {
        transposed[j][i] = m[i][j];
      }
    }
    //2. reverse 
    for(let row of transposed){
    }

    return transposed;

  }

  console.log(rotateMatrix([[1,2,3],[4,5,6],[7,8,9]]),
              rotateMatrix([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]));