[백준, 자바, 10989번] 수 정렬하기 3 - 도수 정렬(Counting Sort)

풀이

• 뭔가 간단하게 사용하는 sort() 메서드들로는 
• 메모리 초과가 발생하기에 찾아보니
• 도수 정렬이라는 걸 활용해야한다고 했다.
• 그래서 다른 포스팅된 게시글을 확인했을땐 뭔가 어렵게 느껴져서
• GPT하고 이야기해보니 정말 간단하게
• 해당 값에 대한 인덱스의 값을 카운팅하는 것으로
• 요소간 비교가 아니기에 모든 데이터를 한 번씩만 접근해서
• 범위 조건이 있는 경우 한정하에 굉장히 빠르게 처리가 가능하다는 걸 알 수 있었다.
• 그래서 아래와 같이 코드를 작성하여 해결
• 물론 기존 도수 정렬 방식과는 다르게 
  • 원래 방식은 입력 값에 대한 최댓값 - 최솟값 + 1에 해당하는 만큼
    배열을 만들어야 했지만
  • 값을 받아오는 대로 넣어 처리하고자 하여 최댓값인 10.000에서 0번째 인덱스를 생각하여
  • 10.001만큼 크기를 정하고 이후 입력 값에 해당하는 인덱스를 카운팅하고
  • 이후 해당 인덱스의 값이 0이 아닐 경우만 계속해서 저장 후 최종적으로 출력하여 해결

 

import java.io.*;

public class _10989 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] li = new int[10001];

        for (int i=0; i<n; i++) li[Integer.parseInt(br.readLine())]++;

        for (int i=0; i<10001; i++) {
            while (li[i] != 0) {
                bw.write(i+"\n");
                li[i]--;
            }
        }
        bw.flush();
    }
}