[알고리즘] LeetCode - 48. Rotate Image

보통인부·2020년 8월 7일

노가다 알고리즘

목록 보기

6/10

Description

Given an n by n 2D matrix representing an image.
Rotate the image by 90 degrees(clockwise).
(번역) 이미지를 나타내는 n x n 매트릭스가 주어졌을 때, 이미지를 90도(시계방향) 회전한 결과를 리턴하라.

Note

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.
(번역) 별도의 2D 매트릭스를 생성하지 않고 in-place하게 Input으로 주어진 매트릭스를 수정하라.

Example

Input matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
],

rotated = [
  [7, 4, 1],
  [8, 5, 2],
  [9, 6, 3],
]

풀어보자

In-place??

사실 그냥 회전시키는 건 그렇게 어렵지 않다. 각각의 row를 새로운 매트릭스의 대응되는 컬럼으로 변환시켜주기만 하면 된다. 그런데 In-place라는 조건이 붙으면 좀 고민을 해야한다.

위 방식으로는 결국 n의 auxiliary space가 필요하다.

어쩌라고 그래서!!

매트릭스의 바깥에서 부터 한겹한겹 돌려주면 된다.

첫번째

바깥 프레임의 시작 인덱스를 start, 끝 인덱스를 end, 현재 index를 i라고 하면

const temp = matrix[start][i]
matrix[start][i] = matrix[end - (i - start)][start]
matrix[end - (i - start)][start] = matrix[end][end - (1 - start)]
matrix[end][end - (i - start)] = matrix[i][end]
matrix[i][end] = temp

위와 같은 방식으로 4면의 회전이 가능하다.
이 때 필요한 auxiliary space는 첫 번째 요소를 담아둘 temp 변수 하나면 충분하다.
주의 할 점은 i의 iteration은 start에서 부터 end 전까지 해야한다는 점이다. 그렇지 않으면 각 꼭지점의 요소가 두번 회전되는 결과가 생긴다.

위 과정을 이걸 매트릭스 사이즈의 절반만큼 반복해주면 된다.

구현 코드

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function (matrix) {
  let start = 0;
  let end = matrix.length - 1;
  while (start < end) {
    rotateFrame(matrix, start, end);
    start++;
    end--;
  }
  return matrix;
};

function rotateFrame(matrix, start, end) {
  let temp = 0;
  for (let i = start; i < end; i++) {
    temp = matrix[start][i];
    matrix[start][i] = matrix[end - (i - start)][start];
    matrix[end - (i - start)][start] = matrix[end][end - (i - start)];
    matrix[end][end - (i - start)] = matrix[i][end];
    matrix[i][end] = temp;
  }
}