JavaScript로 matrix 회전 알고리즘 구현하기

🐶·2021년 7월 18일
0

알고리즘

목록 보기
15/21

문제

2차원 N x N 배열을 시계 방향으로 90도 회전시킨 배열을 리턴해야 합니다.
세로와 가로의 길이가 각각 M, N인 2차원 M X N 배열을 시계방향으로 90도씩 K번 회전시킨 배열을 리턴해 보세요. 회전수가 두 번째 입력으로 주어집니다.

수도코드

회전수에 대한 규칙은 아래와 같이 정립하였다.

//k가 4로 나눴을 때 나머지가 1, 2, 3, 0이냐에 따라서 다름
  //나머지가 1일 때
  //나머지가 2일 때 --> matrix를 reverse 두번... (행열 한번씩)
  //나머지가 3일 때 --> 1의 결과를 reverse 두번... (행열 한번씩)
  //나머지가 0일 때 --> matrix 그대로임

나머지가 1일 때 행렬의 요소들을 90도씩 돌리는 것은 아래와 같이 접근하였다.

90도 회전 후의 배열을 result라고 한다면...
//matrix의 한 '요소' 길이가 result 배열의 길이임
//따라서 그 길이만큼 빈배열[]을 채워넣어놓고
//이중반복문으로 요소를 하나하나 90도 회전한 위치에 넣는데

//matrix는 0번째 요소부터 추출하지만 result에서는 끝에서부터 채워지므로
//일단 result에 0부터 채워넣은 다음 reverse를 해준다!(이 문제의 포인트)

코드로 나타내보면

const rotateMatrix = function (matrix, k) {

  if(matrix.length ===0) return []
  
  let result = [];
  for(let i=0; i<matrix[0].length; i++){
    result.push([]); 
  }
  for(let j=0; j<matrix[0].length; j++){
    for(let i=0; i<matrix.length; i++){
        result[j].push(matrix[i][j]) //matrix의 세로방향 요소들을 result의 가로방향 요소들로 import!
    } 
    result[j].reverse(); //그리고 result의 요소들은 reverse
  } //90도 돌렸을 때 result배열 만들기 완성!
  
  
  if(k%4 === 0){ //4로 나누고 나머지가 0일때
    return matrix;
  }
  else if(k===undefined || k%4 === 1){ //나머지가 1일 때 위에서 구해놓은 result 바로 반환 
    return result;
  }
  else if(k%4 ===2){ 
    for(let j=0; j<matrix.length; j++){
      matrix[j].reverse(); //행렬의 각 요소를 reverse하고
    }
    matrix.reverse(); //행렬 전체도 한번 reverse
    return matrix;
  }
  else{
    for(let j=0; j<result.length; j++){
      result[j].reverse();
    }
    result.reverse();
    return result;
  }

};
profile
우당탕탕 개발일기📝🤖

0개의 댓글