[알고리즘] rotateMatrix, radixSort

두 문제는 시간이 없어 제대로 살펴보지 못해서 블로깅하면서 찬찬히 살펴보려고 한다.

rotateMatrix

2차원 N x N 배열을 시계 방향으로 90도 회전시킨 배열을 리턴해야 함.
rotateMatrix 함수는 인자로 matrix를 받는데 matrix는 가로 길이(matrix[i].length)와 세로 길이(matrix.length)가 모두 N인 2차원 배열이고 matrix[i][j]는 number 타입이다.
출력 역시 2차원 배열을 리턴해야 한다.

advanced

전달 인자를 하나더 추가해서 90도로 k번 회전시킨 배열을 리턴하라.

const rotateMatrix = function (matrix, rotateNum = 1) {
  // rotateNum 이 0일 수 있으므로 아래와 같은 초기화는 지양해야 함
  // rotateNum = rotateNum || 1
  
  const N = matrix.length;
  // 빈 배열을 입력받을 수 있으므로 &&를 통해 matrix[0]이 true일 때 matrix[0].length 값을 할당한다. 
  //만약 matrix[0]값이 false이면 평가 결과가 false가 되고, M에 false가 할당된다. 
  const M = matrix[0] && matrix[0].length;

  
  //4번 회전하면 360도로 제 자리로 돌아오므로, 90도로 나눈 뒤 나머지만 돌려주면 된다. 
  rotateNum = rotateNum % 4;
  
  // 회전하지 않는다.
  if (rotateNum === 0) return matrix;

  //회전한 배열 담을 rotated 만들어주기 
  const rotated = [];
  
  
  // 홀수번 회전 시 M x N, 짝수번 회전 시 N x M
  // 행과 열을 배열에 담아놓고 아래 반복문을 돌릴 때 사용한다. 
  const RC = rotateNum % 2 === 1 ? [M, N] : [N, M];

  //행은 배열 내 2차원 배열들의 개수 
  for (let row = 0; row < RC[0]; row++) {
    rotated[row] = [];
    
    //열은 만들어진 행들에 회전한 요소들 차례로 넣어준다.
    for (let col = 0; col < RC[1]; col++) {
      if (rotateNum === 1) rotated[row][col] = matrix[N - col - 1][row];
      else if (rotateNum === 2)
        rotated[row][col] = matrix[N - row - 1][M - col - 1];
      else rotated[row][col] = matrix[col][M - row - 1];
    }
  }

  return rotated;
};

radixSort

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 한다.
arr.sort 사용이 금지되며, 기수 정렬을 구현해야 한다.
입력으로 주어진 배열은 중첩되지 않은 1차원 배열이다.

힌트

• 기수 정렬은 내부적으로 계수 정렬을 사용한다

기수정렬 : 데이터의 각 자릿수를 낮은 자리부터 가장 큰 자릿수까지 올라가면서 정렬을 수행한다.
이런 이유 때문에 자릿수가 존재하지 않는 데이터를 기수정렬로 정렬하는 것은 불가능하다.
비교 연산을 수행하지 않아 조건이 맞는 상황에서 빠른 정렬 속도를 보장한다.
계수정렬 : 배열 내에서 특정한 값이 몇 번 등장했는지에 따라 정렬을 수행한다. (비교연산이 사용X)

참고 블로그

advanced

arr[i]의 범위가 정수 전체로 확대될 경우, 기수 정렬 알고리즘을 완성해 보세요.

//배열에서 제일 큰 수를 구하는 함수 
function getMax(arr) {
  return arr.reduce((max, item) => {
    if (item > max) return item;
    return max;
  }, 0);
}

function countingSort(arr, radix) {
  const N = arr.length;
  const output = Array(N).fill(0);
  const count = Array(10).fill(0);

  // 현재 자리수를 기준으로 0~9의 개수를 센다.
  arr.forEach((item) => {
    const idx = Math.floor(item / radix) % 10;
    count[idx]++;
  });

  // count[i]가 i까지의 누적 개수가 되도록 만든다.
  count.reduce((totalNum, num, idx) => {
    count[idx] = totalNum + num;
    return totalNum + num;
  });

  // 아래 속성이 유지되도록 하기 위해 배열을 거꾸로 순회한다.
  //  1. 가장 큰 값을 먼저 본다.
  //  2. 가장 큰 값을 가장 마지막에 놓는다.
  let i = N - 1;
  while (i >= 0) {
    const idx = Math.floor(arr[i] / radix) % 10;
    // count[idx]: 현재 radix의 idx까지 누적 개수
    // count[idx]개만큼 있으므로, 인덱스는 count[idx] - 1
    output[count[idx] - 1] = arr[i];
    count[idx] -= 1;
    i--;
  }

  return output;
}

// naive solution
// 양의 정수만 정렬 가능
// function radixSort(arr) {
//   const max = getMax(arr);
//   let radix = 1;
//   while (parseInt(max / radix) > 0) {
//     arr = countingSort(arr, radix);
//     radix *= 10;
//   }
//   return arr;
// }

// 음의 정수를 포함한 기수 정렬
// 1. 주어진 배열을 음수 부분과 양수 부분으로 나눈다.
// 2. 음수는 절대값을 기준으로, 즉 양수로 변환하여 기수 정렬한다.
// 3. 양수를 정렬한다.
// 4. 정렬된 음수 부분을 다시 음수로 바꾸고 순서를 뒤짚는다.
// 5. 음수 부분과 양수 부분을 붙인다.
function radixSort(arr) {
  let left = [];
  let right = [];
  arr.forEach((item) => {
    if (item >= 0) right.push(item);
    else left.push(item * -1);
  });

  let max = getMax(left);
  let radix = 1;
  while (parseInt(max / radix) > 0) {
    left = countingSort(left, radix);
    radix *= 10;
  }

  max = getMax(right);
  radix = 1;
  while (parseInt(max / radix) > 0) {
    right = countingSort(right, radix);
    radix *= 10;
  }

  return left
    .reverse()
    .map((item) => item * -1)
    .concat(right);
}