Leetcode

48. Rotate Image

uncertainty

Algorithm

Leetcode

48. Rotate Image

Medium

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Plain Text
복사

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Plain Text
복사

Example 3:

Input: matrix = [[1]]
Output: [[1]]
Plain Text
복사

Example 4:

Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]
Plain Text
복사

Constraints:

•

matrix.length == n

•

matrix[i].length == n

•

1 <= n <= 20

•

1000 <= matrix[i][j] <= 1000

My solution

in-place ? 

생각을 전환해야 한다. 알고리즘을 어떻게 짜야 공간을 아낄 수 있을까?

intro sort에서 자주 이용되는, 복잡도가 n^2짜리인 정렬 알고리즘인 insertion sort는 어떨까요? 이것 역시 추가적인 공간을 그리 많이 소모하지 않습니다.

로직을 잘 생각해 봅시다. 이미 정렬된 것들은 노란색으로 표시했습니다. 그리고 현재 턴에 올바른 자리에 들어가야 할 원소는 군청색으로 표시해 두었는데요. 2가 들어갈 자리는 1과 4 사이입니다.

그러면 노란색 뒤에, 주황색 앞에 들어가야 할 겁니다. 따라서, 주황색으로 표시된 것들을 뒤로 1칸 밀어버립니다.

다음에 군청색으로 표시된 것이 주황색 앞에 옵니다. 이 과정은 추가적인 메모리가 필요하지 않습니다. 단지, 군청색이 어떤 원소였는지만 저장해 두고, 주황색 부분만 뒤에 있는 원소부터 1칸씩 뒤로 밀어버리기만 하면 되기 때문입니다. 배열의 크기가 500만이 되도, 끽 해봐야 현재 턴에 위치를 찾아야 할 수를 저장할 공간하고, 배열의 특정 위치를 가리키는 포인터 몇 개만 관리하면 됩니다. 이는 500만보다 한참 작은 수치입니다. 따라서 insertion sort는 in place 하다고 할 수 있어요.

https://codingdog.tistory.com/entry/in-place-알고리즘에-대해서-간단하게-알아봅시다

어쨌든 딱 90도만큼 시계방향으로 돌린 배열을 구하면 된다. 1~2개 정도의 변수만 있으면 돌릴 수 있을 거 같다.

변수는 네 개의 원소를 가진 배열이어야 할듯. 한방에 하나의 배열씩 바꿔줘야지

돌릴 것 이전에 원래 위치인 [5, 1, 9, 11]을 저장해두고 있어야 된다. 4번은 돌려야 가장자리가 다바뀜.

const rotate = function (matrix) {
  const n = matrix.length;
  console.log(matrix);
  for (let i = 0; i < n; i++) {
    const temp = matrix[i].slice(i, n - i);
    let t = [];
    for (const x of matrix) {
      t = [...temp2, x[n - i - 1]];
    }
    temp2 = t.slice(i, n - i);

    let temp2 = [];
    for (const x of matrix) {
      temp2 = [...temp2, x[n - i - 1]];
    }
    temp2 = temp2.slice(i, n - i);

    const temp3 = matrix[n - i - 1].slice(i, n - i);

    if (temp.length === 1) return;

    console.log(temp, temp2, temp3);
  }
};
JavaScript
복사

이렇게 복잡하게 생각하면 안될 거 같다.

아래의 경우는 위에서 str을 중앙 기준으로 양옆을 교환하면서 앞뒤를 바꾸는 것과 같은 방식이다.

j는 0부터 시작해서 N/2(중앙)까지만 도착하면 양옆이 모두 변경된 것이다. 따라서 N/2보다 작을 때까지를 범위로 둔다.

for (let i = 0; i < N; ++i) {
    for (let j = 0; j < N / 2; ++j) {
JavaScript
복사

이렇게 앞뒤를 바꾸는 방식은 알아두면 굉장히 좋을 것 같다. 마지막에 0,2와 0,2를 바꾸게 된다.

i, j i, N - j - 1 (이건 N-1 그러니까 최대 인덱스에서 j만큼 뺀만큼이다.)

이걸 서로 바꿔준 것이다.

결과적으로 matrix가 reverse horizontally된다.

48. rotate image C++ 풀이

https://leetcode.com/problems/rotate-image [ Rotate Image - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

https://ellerymoon.tistory.com/18

위의 방식이 더 편하지만 훨씬 더 빠른 방식이 있긴 하다. 2중 for문을 한번만에 끝내는 방식이다. 이게 가장 빠른 것 같다.

for (let k = 0; k < matrix.length / 2; k++) {
    for (let i = k; i < matrix.length - 1 - k; i++) {
      const temp = matrix[k][i];
      matrix[k][i] = matrix[matrix.length - 1 - i][k];
      matrix[matrix.length - 1 - i][k] = matrix[matrix.length - 1 - k][matrix.length - 1 - i];
      matrix[matrix.length - 1 - k][matrix.length - 1 - i] = matrix[i][matrix.length - 1 - k];
      matrix[i][matrix.length - 1 - k] = temp;
    }
  }
  return matrix;
JavaScript
복사

그리고 가독성이나 성능이 조금 더 높은게 있는데 이건 먼저 전치행렬화를 하는데 행과 열을 뒤바꾸는 게 아니라

이렇게 이동시킨다. 그리고 for문 하나로 위 아래로 뒤바꾼다.

// # : 3
  const N = matrix.length;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N - i; j++) {
      [matrix[i][j], matrix[N - 1 - j][N - 1 - i]] 
= [matrix[N - j - 1][N - i - 1], matrix[i][j]];
    }
  }
  for (let i = 0; i < N / 2; i++) {
    [matrix[i], matrix[N - 1 - i]] = [matrix[N - 1 - i], matrix[i]];
  }
JavaScript
복사

소스코드

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
const rotate = function (matrix) {
  // # : 1
  // for (let k = 0; k < matrix.length / 2; k++) {
  //   for (let i = k; i < matrix.length - 1 - k; i++) {
  //     const temp = matrix[k][i];
  //     matrix[k][i] = matrix[matrix.length - 1 - i][k];
  //     matrix[matrix.length - 1 - i][k] = matrix[matrix.length - 1 - k][matrix.length - 1 - i];
  //     matrix[matrix.length - 1 - k][matrix.length - 1 - i] = matrix[i][matrix.length - 1 - k];
  //     matrix[i][matrix.length - 1 - k] = temp;
  //   }
  // }
  // return matrix;
  // # : 2
  const N = matrix.length;
  // & : i <-> j : 전치행렬화, 행과 열을 swap
  for (let i = 0; i < N; ++i) {
    for (let j = i; j < N; ++j) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  console.log(matrix);

  for (let i = 0; i < N; ++i) {
    for (let j = 0; j < N / 2; ++j) {
      console.log(i, j, '/', i, N - j - 1, '/', matrix[i][j], matrix[i][N - j - 1]);

      [matrix[i][j], matrix[i][N - j - 1]] = [matrix[i][N - j - 1], matrix[i][j]];
    }
  }

  console.log(matrix);

  return matrix;
};

// test('TC1', () => {
//   expect(
//     rotate([
//       [5, 1, 9, 11],
//       [2, 4, 8, 10],
//       [13, 3, 6, 7],
//       [15, 14, 12, 16],
//     ])
//   ).toStrictEqual([
//     [15, 13, 2, 5],
//     [14, 3, 4, 1],
//     [12, 6, 8, 9],
//     [16, 7, 10, 11],
//   ]);
// });
test('TC2', () => {
  expect(
    rotate([
      [5, 1, 9, 11, 17],
      [2, 4, 8, 10, 18],
      [13, 3, 6, 7, 19],
      [21, 22, 23, 24, 25],
      [15, 14, 12, 16, 20],
    ])
  ).toStrictEqual([
    [15, 21, 13, 2, 5],
    [14, 22, 3, 4, 1],
    [12, 23, 6, 8, 9],
    [16, 24, 7, 10, 11],
    [20, 25, 19, 18, 17],
  ]);
});

// test('TC3', () => {
//   expect(rotate([[1]])).toStrictEqual([[1]]);
// });
// test('TC4', () => {
//   expect(
//     rotate([
//       [1, 2],
//       [3, 4],
//     ])
//   ).toStrictEqual([
//     [3, 1],
//     [4, 2],
//   ]);
// });
JavaScript
복사