Toy 문제 24

문제

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

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 0 이상의 정수
• arr.length 100,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• 기수 정렬을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

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

 

 

수도코드(해석)

기수정렬을 사용하는 문제입니다. 기수정렬은 낮은 자리수 부터 비교하여 정렬해간다는 것을 기본 개념으로 하는 정렬 입니다.

시간 복잡도는 O(d * (n + b)) == O(dn)으로 매우 빠른편이지만 부동 소숫점 실수 같이 자릿수가 없는 경우 정렬할 수 없는 것이 단점 입니다.

 

여러 블로그를 참고했지만 이 이미지가 제일 이해하기 쉽고 간결해 보입니다.(참고출처)

 

1의 자리 기준으로 크기를 정렬하고

10의 자리기준으로 크기를 정렬한다음 순서대로 정렬하는 방식입니다.

 

해당 문제에서 Advanced는 정수까지 확대 즉, 음수도 가능하게 요구하고 있습니다.

1. 주어진 배열을 음수 부분과 양수 부분으로 나눈다. 

2. 음수는 절대값을 기준으로, 즉 양수로 변환하여 기수 정렬한다. 

3. 양수를 정렬한다. 

4. 정렬된 음수 부분을 다시 음수로 바꾸고 순서를 뒤짚는다. 

5. 음수 부분과 양수 부분을 붙인다.

위와 같은 과정을 거치면 됩니다.

 

코드에 어려운 점은 없지만 익숙치 않은 부분이기 때문에 복습하여 다시 풀어보는게 중요할 것 같습니다.

 

 

 

코드(Reference)

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




// 음수포함 기수정렬 실행코드
function radixSort(arr) {
  let left = [];
  let right = [];
  arr.forEach((item) => {
    if (item >= 0) right.push(item);
    else left.push(item * -1);
  });
// 음수부분은 left
  let max = getMax(left);
  let radix = 1;
  while (parseInt(max / radix) > 0) {
    left = countingSort(left, radix);
    radix *= 10;
  }
// 양수부분은 Right
  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);
}