본문 바로가기
CS/Algorithm

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

by JiGyeong 2019. 4. 1.

기수정렬 (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 메소드를 분리해서 짠 다음에 음수와 양수로 나누어 두 번 돌렸습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
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;
    }
}
cs