radixSort

문제

---

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

입력

---

인자 1 : arr

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

출력

---

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

주의사항

---

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

입출력 예시

나의 코드

결과

소스코드

function radixSort(arr) {
  // 먼저 입력 받은 배열을 양수 배열과 음수 배열로 나눈다.
  let negativeArr = [];
  let positiveArr = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < 0) {
      negativeArr.push(arr[i]);
    } else {
      positiveArr.push(arr[i]);
    }
  }
  // 재귀 함수를 실행한다.
  // 음수 배열의 경우, 순서가 역순으로 되어있기 때문에 뒤집는 reverse 메소드 사용
  // 음수 배열과 양수 배열을 spread 로 합친 배열을 최종적으로 리턴한다.
  // 처음엔 1의 자릿수를 판단하기 위해 재귀함수의 입력인자로 10과 1을 넣는다.
  // ex) 123의 1의 자릿수를 구하는 방법은 123%10/1 이기 때문
  return [...recur(negativeArr, 10, 1).reverse(), ...recur(positiveArr, 10, 1)];
}

const recur = function (arr, x, y) {
  // 입력인자는 arr, x, y
  // x와 y는 숫자의 자릿수를 구하기 위한 변수로 활용
  if (y === 1000000) {
    // 입력받은 배열 요소의 숫자의 상한이 100만 미만(999,999)으로 가정
    // 100만번째 수의 자릿수를 구하는 변수가 들어올 때 종료한다.
    return arr.flat();
  }
  // 길이 10의 2차원 배열을 만든다.
  let cntArr = new Array(10).fill(0).map((el) => new Array(0));
  // 입력인자 배열을 순회하며 그 배열의 자릿수에 해당하는 인덱스에 삽입한다.
  for (let i = 0; i < arr.length; i++) {
    // 음수 배열일 경우도 생각하여 절댓값으로 바꾼다.
    cntArr[Math.floor((Math.abs(arr[i]) % x) / y)].push(arr[i]);
  }
  // 배열의 요소들 중 예를 들어 1의 자릿수가 같은 요소가 있을 수 있다.
  // 재귀를 실행하기 위해 이 배열을 펼치고 입력 인자로 넣어준다.
  // 1의 자리를 모두 구했으면 이제 10의 자릿수를 구하기 위해 x, y 입력인자에 각각 10을 곱하여 재귀호출한다.
  return recur(cntArr.flat(), x * 10, y * 10);
};