기수정렬 (Radix Sort) , 백준 2751 Java

기수정렬 (Radix Sort) , 백준 2751 Java

정수의 자리수의 숫자를 기준으로 큐에 넣어서 순서대로 꺼내는 방식으로 정렬을 기준이 되는 자리수를 바꿔가면서 정렬을 하는 알고리즘

아래와 같은 수가 있을 경우

 

65

22

125

83

9

70

 

첫번째,

배열 뒤부터 조회하며

 

65

22

125

83

9

70

 

일의 자리수를 기준으로 큐에 넣는다.

 

					65
70		22	83		125				9
0	1	2	3	4	5	6	7	8	9

 

그리고 9부터 큐에서 꺼내 배열에 넣는다.

 

70

22

83

65

125

9

 

십의 자리수를 기준으로 큐에 넣는다.

 

		22
9		125				65	70	83
0	1	2	3	4	5	6	7	8	9

 

그리고 9부터 큐에서 꺼내 배열에 넣는다.

 

9

22

125

65

70

83

 

세번째,

백의 자리수를 기준으로 큐에 넣는다.

 

9
22
65
70
83	125
0	1	2	3	4	5	6	7	8	9

 

그리고 9부터 큐에서 꺼내 배열에 넣는다.

 

9

22

65

70

83

125

 

장점

아무리 큰 배열일지라도, 항상 O(n) 의 복잡도를 유지한다.
안정정렬이다. ( 데이터들 간의 상대적 순서 유지)

 

단점

정수와 같은 자료에서만 사용 가능하다.
소수점이 붙거나, 숫자가 아닐 경우에는 사용할 수 없다.

 

백준 2751 : 수 정렬하기 2

https://www.acmicpc.net/problem/2751

문제를 기수정렬로 풀어보았습니다.

이 문제에서 유의할 점은 음수와 양수를 분리해서 생각해야 한다는 것입니다.

저는 Radix Sort 메소드를 분리해서 짠 다음에 음수와 양수로 나누어 두 번 돌렸습니다.

 

import java.io.IOException;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
 
public class Problem2751_Radix {
 
    public static void main(String[] args) throws IOException {
 
        // 1. 변수 선언
        Queue<Integer> pQue = new LinkedList();
        Queue<Integer> nQue = new LinkedList();
        int pArr[] = null; // 양수
        int nArr[] = null; // 음수
        int N = 0;
        
        Scanner sc = new Scanner(System.in);
 
        // 2. 입력을 스캔받음
        N = sc.nextInt();
        
        int input = 0;
        int idx = 0;
        while (idx < N) {
            
            input = sc.nextInt();
            
            if(input < 0) nQue.add(input);
            else pQue.add(input);
            
            idx++;
        }
        
        
        pArr = new int[pQue.size()];
        nArr = new int[nQue.size()];
        
        for(int i=0; i<pArr.length; i++) {
            pArr[i] = pQue.poll();
        }
        for(int i=0; i<nArr.length; i++) {
            nArr[i] = nQue.poll();
        }
        
        // radixSort 돌림
        pArr = radixSort(pArr);
        nArr = radixSort(nArr);
 
        StringBuilder sb = new StringBuilder();
        
        // 음수 정렬
        for(int i=nArr.length-1; i>=0; i--) {
            sb.append((int)nArr[i]+"\n");
        }
        
        // 양수 정렬
        for (Integer i : pArr) {
            sb.append((int) i + "\n");
        }
        
        System.out.println(sb);
    }
 
    static int[] radixSort(int[] arr) {
        
        int sortArr[] = new int[arr.length];
        int queSize, max_length = 0;
        int lenght = 0;
        int idx= 0;
        
        Map<Integer, Queue> map = new HashMap<>();
        
        for (int l : arr) {
            lenght = (int) Math.log10(Math.abs(l))+1;
            if(max_length < lenght) {
                max_length = lenght;
            }
        }
        
        // map 초기 세팅
        for (int j = 0; j < 10; j++) {
            map.put(j, new LinkedList<Integer>());
        }
 
        // 최대 자리수 만큼 반복
        for (int i = 0; i < max_length; i++) {
 
            // map 초기화
            for (int j = 0; j < 10; j++) {
                map.get(j).clear();
            }
 
            for (int j = arr.length - 1; j >= 0; j--) { // 배열의 뒤부터 Hash Map에 인덱싱해서 담음
                map.get((int) (Math.abs(arr[j]) / Math.pow(10, i) % 10)).add(arr[j]);
            }
 
            // 4. 9부터 Map에서 꺼내 sortArr에 담음
            idx = arr.length - 1;
            for (int j = 9; j >= 0; j--) {
 
                queSize = map.get(j).size();
                for (int qIdx = 0; qIdx < queSize; qIdx++) {
                    sortArr[idx] = (Integer) map.get(j).poll();
                    idx--;
                }
            }
 
            // 5. arr에 sortArr 복사
            System.arraycopy(sortArr, 0, arr, 0, arr.length);
        }
        return arr;
    }
}