[백준 10989] 수 정렬하기 3 (JAVA)

백준 10989번 문제  - 수 정렬하기 3

10989번: 수 정렬하기 3

---

문제 분석

 

 

: 오름차순으로 정렬해서 출력해라

---

해결 키 포인트

 

• 오름차순 정렬
  
  • Arrays.sort() 사용
  • 기수 정렬 사용
• 중요한 포인트는 메모리 제한(JAVA일 경우, 512MB)을 지켜야 한다는 것이다.
  • 최대 10,000,000개의 데이터를 입력 받은 후에 데이터를 정렬해야하는데 512MB는 메모리 제한을 고려해서 코딩해야한다는 것
  • 기수배열 정렬할 때 최대 세개의 배열 사용 가능
    1. int [] nums = new int [N] → 실제 입력 및 출력 할 배열
    2. int [] list = new int [N] → 중간 합치는 과정을 도와줄 배열
    3. int [] teMul = new int [10] → 해당 자리수로 나눌 때 필요한 배열
• 시간 제한(JAVA일 경우, 3초)를 지켜야 한다는 것이다.

 

---

어려움을 겪은 부분

 

Arrays.sort()를 이용하면 가장 편리하지만, 배움을 위해 기수 정렬을 시도해보려 하였다.

 

기수 정렬을 사용할 때, 어려웠던 점은 다음과 같다.

1. 단순 queue를 10개 만들어서 일의 자리수부터 각 자리수에 해당하는 queue에 삽입시키고, 합치고, 삽입시키는 것을 반복하는 코딩.
   → 메모리 초과
2. 각 자릿수에 따라서 어떻게 배열을 정렬할 수 있는지 고민
   → 각 자릿수에 따른 값들의 개수를 구하고, 더해서 해당 자릿수일 경우, 그 자리수 위치에 삽입
   (해당 자릿수 끝 인덱스 계산후, 끝 배열부터 집어넣어 점차 줄여나가는 방향으로 코딩)
3. boolean 변수를 제작해, 더 이상 나누지지 않을 때까지 while 반복문으로 코딩 → 시간 초과
   → 문제 원인 파악
   • if(nums[i]/tenMul > 0) → if(isClear && nums[i]/tenMul > 0) 변경
     이미 isClear가 true이면 뒤에 확인 할 필요 없는데, 사용함으로 시간이 지연됨

 

---

기수 정렬 설명

 

값을 비교하지 않는 특이한 정렬로, 값을 놓고 비교할 자릿 수를 정한 다음 해당 자릿수만 비교한다.

기수 정렬은 10개의 큐를 이용하며, 각 큐는 값의 자릿수를 대표한다.

 

Do it! 알고리즘 코딩 테스트 기본

 

---

코드

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

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

        // N 입력
        int N = Integer.parseInt(br.readLine());

        // 수 입력
        int nums [] = new int[N];
        for(int i=0;i<N;i++) {
            nums[i] = Integer.parseInt(br.readLine());
        }
        br.close();

        // Arrays.sort 정렬
//        Arrays.sort(nums);

        // 기수 정렬
        radixSort(nums);

        // 출력
        for(int i=0;i<N;i++){
            bw.write(nums[i]+"\n");
        }

        bw.flush();
        bw.close();
    }

    public static void radixSort(int [] nums) {
        int [] list = new int[nums.length];

        int tenMul = 1;
        boolean isClear = false;

        // 더 이상 tenMul보다 큰 수가 없을 때 까지
        while(!isClear) {
            isClear = true;

            int [] bucket = new int [10];
            // 배열에 담긴 수를 가지고 현재 tenMun번째 자리수에 있는 개수 알아내기
            // bucket[i] = i번째 자리수에 있는 수 개수
            for(int i=0;i<nums.length;i++){
                bucket[(nums[i]/tenMul)%10]++;
                if(isClear && nums[i]/tenMul > 0) {
                    isClear = false;
                }
            }

            // bucket[i]를 가지고 i번째 개수의 끝 개수 알아내기
            for(int i=1;i<10;i++) {
                bucket[i] += bucket[i-1];
            }

            // bucket을 기준으로 1차 정렬된 list 생성
            for(int i=nums.length -1; i>=0; i--){
                list[bucket[(nums[i]/tenMul)%10]-1] = nums[i];
                // bucket 크기 줄이기
                bucket[(nums[i]/tenMul)%10]--;
            }

            // 원본 배열 다시 정렬
            for(int i=0; i<list.length; i++){
                nums[i] = list[i];
            }

            tenMul *= 10;
        }
    }
}