문제 : radixSort

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

let output = radixSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

문제의 접근

끝난줄 알았는데 아직 안 끝난 정렬 문제다... 일단 기수 정렬의 개념을 이해하고 그대로 코드를 작성해보았다.

function radixSort(arr) {
  // todo: 여기에 코드를 작성합니다.
  let buket = [[],[],[],[],[],[],[],[],[],[]]
  let max = 0;

  for(let el of arr){
    let target = String(el)
    if(target.length > max){
      max = target.length
    }
  }
  while(max >= 0){
    while(arr.length > 0){
      let target = arr.shift();
      let num = String(target)[max-1]
      if(!num){
        buket[0].push(target)
      }else{
        let i = Number(num)
        buket[i].push(target)
      }
    }

    for(let i = 0; i < 10; i++){
      arr = [...arr, ...buket[i]]
    }
    buket = [[],[],[],[],[],[],[],[],[],[]]
    max--;
  }
  return arr;
}

당연하게도 콘솔은 잘 나오지만 테스트는 통과 못하고 있다. 이제는 진자 욕이 나오려한다. 개념을 이해하면 뭐하나 결국 안되는데... 진짜 아무리 생각해도 시간초과가 나오는 이유를 모르겠다.

문제를 통해 생각해 볼 것

이 문제는 그냥 레퍼런스를 보고 이해하는 수 밖에 없을 것 같다. 어찌됬든 기수정렬은 확실히 이해했기 때문에

function getMax(arr) {
  return arr.reduce((max, item) => {
    if (item > max) return item;
    return max;
  }, 0);
} // 배열에서 최대값을 뽑아내는 함수

function countingSort(arr, radix) { // arr = [3,1,21], radix = 1 (자릿수)
  const N = arr.length; // arr의 길이 3
  const output = Array(N).fill(0); // [0,0,0]
  const count = Array(10).fill(0); // [0,0,0,0,0,0,0,0,0,0]

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

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

  // 아래 속성이 유지되도록 하기 위해 배열을 거꾸로 순회한다.
  //  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; // [1,21,3]
}

// 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);
} // 정렬된 왼쪽값을 뒤집어서 다시 음수로 만들어준뒤 오른쪽 값들을 합쳐준다.

부품이 되는 함수들만 이해한다면 메인 함수는 쉽게 이해가 가능했다. 하지만 countingSort 함수를 이해하는데 조금 오래 걸렸다.

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

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--;
  }

그 중에서 이 부분 왜 누적을 해주는지 이해하지 못했지만 다음 코드를 보고 확실히 이해할 수 있었다. 간단히 예를 들어서 설명하자면

index 값의 자리숫자는 최소 아웃풋 결과에서 count[index]-1값 안쪽에 위치해야한다.

가령 [3,1,21]의 경우 1의 자리 숫자가 1인수가 두개 있기 때문에 1의자리 숫자가 3인 수는 최소한 3번째부터 들어갈 수 있다는 말이다.