정렬. 3단계
10989번. 수 정렬하기 3

문제

10989번 문제 링크

이번 문제는 맞게 풀더라도, 백준 사이트 node.js 언어의 메모리 문제로 인해 JS로는 풀 수 없다고한다.
이 부분에 대해서 업데이트가 될 예정이라고하니, 언젠가는 풀 수 있을 것이다.
참고바랍니다.

계수 정렬(Counting Sort)

이 문제의 핵심은 계수 정렬(Counting Sort)를 사용하는 것이라고 한다.
시간 복잡도가 N으로 상당히 빠른 정렬 속도를 가지는 방법인데,
정렬해야할 수의 범위가 적을 때에만 유용하다고 한다.
방식은 다음과 같다.

1. 정렬해야할 배열을 확인한다.
2. 1번 배열 원소의 최대값을 배열 길이로 하는 새로운 배열을 생성한다.
3. 1번 배열의 특정 값을 2번에서 만든 배열의 인덱스에 맞춰서 카운트를 증가시킨다.
4. 반복문 등을 통해 해당 인덱스의 카운트만큼 인덱스 값을 출력한다.

말로만 들으면 사실 이해가 안된다.
코드를 보면서 이해해보자.

solution

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map((item) => Number(item));

// input 배열의 최댓값을 찾는다.
const max = Math.max(...input);

// max + 1만큼 길이를 가지는 배열을 만들고, 0으로 채워준다.
// max만큼만하면 0번째 인덱스에 자연수 1에 해당하는 정보가 들어가서 헷갈릴 수 있기 때문.
const array = new Array(max + 1).fill(0);

// input 배열의 길이만큼 반복하면서 각 숫자의 카운트를 증가시킴.
for(let i = 0; i < input.length; i++) {
  // 만약, input 배열의 0번째 인덱스에 숫자 1이 있었다면
  // array 배열의 1번째 인덱스의 값을 증가시킨다.(위에서 0으로 초기화해놨던 것)
  array[input[i]]++;
}

// 위 for문의 연산이 끝나면
// input 배열에 있던 원소 숫자들을 인덱스로 가지는 array 배열의 원소들은
// 0이 아닌 다른 숫자들로 채워져 있을 것이다.
// 만약, input 배열에 숫자 7이 없다면, array 배열의 7번째 인덱스는 0이라는 뜻.
for(let i = 0; i < array.length; i++) {
  // 0은 false이므로 통과되고, 값이 증가한 인덱스들만 조건 만족.
  if (array[i]) {
    // array 배열에서 증가된 카운트만큼 해당 인덱스 출력
    for (let j = 0; j < array[i]; j++) {
      console.log(i);
    }
  }
}

주석을 보면서 따라가면 이해가 좀 더 쉬울 것이라고 생각한다.
예시를 들어서 설명하면 다음과 같다.

input : [5,1,4,2,2,1,5,4]

// 각 숫자의 개수
1 : 2개
2 : 2개
3 : 0개
4 : 2개
5 : 2개

// input 배열의 최댓값
max : 5

// 원소들은 input 배열의 0,1,2,3,4,5의 개수를 의미
array : [0,0,0,0,0,0]

// 첫 번째 for문
숫자별 카운트 시작

array : [0,2,2,0,2,2]

// 두 번째 for문
array 배열의 원소가 0이면 조건 불만족.
다른 숫자라면 조건 만족.

array의 1번 인덱스에 있는 값 : 2 : 숫자 1이 2개 있음을 의미
array의 2번 인덱스에 있는 값 : 2 : 숫자 2가 2개 있음을 의미
array의 4번 인덱스에 있는 값 : 2 : 숫자 4가 2개 있음을 의미
array의 5번 인덱스에 있는 값 : 2 : 숫자 5가 2개 있음을 의미

// 두 번째 for문 내부의 for문
개수만큼 인덱스 번호를 출력

1
1
2
2
4
4
5
5

참고 자료

이번 문제는 이해가 되지않아서, 다른 분들의 풀이 중 가장 이해가 잘 되는 것을 가져왔다.
참고 자료 1