[백준/JAVA] 10989번: 수 정렬하기 3

🔺 문제

10989번: 수 정렬하기 3

 

🔺 코드

- 내 코드 (틀림)

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException{
	    var br = new BufferedReader(new InputStreamReader(System.in));
	    
	    int n = Integer.parseInt(br.readLine());
	    int[] arr = new int[n];          // 수열 원소 : n개
	    int[] counting = new int[10001]; // 수의 범위 : 1 ~ 10000
	    int[] result = new int[n];       // 정렬될 배열
	    
	    // Counting sort
	    // 과정 1
	    for(int i = 0 ; i < arr.length ; i++) {
	        arr[i] = Integer.parseInt(br.readLine());
	        counting[arr[i]]++;
	    }
	    
	    // 과정 2: 누적합 배열 (각 값 : 시작점 - 1)
	    for(int i = 1 ; i < counting.length ; i++) {
	        counting[i] += counting[i-1];
	    }
	    
	    // 과정 3
	    for(int i = arr.length - 1 ; i >= 0 ; i--) {
	        int val = arr[i];
	        counting[val]--;
	        result[counting[val]] = val;
	    }
	    
	    // 정렬된 배열 출력
	    for(int i : result) {
	        System.out.println(i);
	    }
		
	}
}

카운팅 정렬 배운 거 써먹으려고 해봤는데 시간 초과가 떴다..😥

 

 

- 정답 코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException{
	    var br = new BufferedReader(new InputStreamReader(System.in));
	    
	    int n = Integer.parseInt(br.readLine());
	    int[] arr = new int[n];          // 수열 원소 : n개
	    int[] counting = new int[10001]; // 수의 범위 : 1 ~ 10000
	    
	    // Counting sort
	    // 과정 1
	    for(int i = 0 ; i < arr.length ; i++) {
	        arr[i] = Integer.parseInt(br.readLine());
	        counting[arr[i]]++;
	    }
	    
	    br.close();
	    
	    
	    // 과정 2
	    var sb = new StringBuilder();
	    for(int i = 1 ; i < counting.length ; i++) {
	        while(counting[i] > 0) {
	            sb.append(i).append('\n');
	            counting[i]--;
	        }
	    }
	 
	    System.out.println(sb);
	}
}

카운팅 정렬 사용했고, 누적합은 사용하지 않는 출력 과정!

 

---

🔺 다른 풀이들

- 풀이1) Arrays.sort(), StringBuilder 사용

[Java] 백준 10989번 [수 정렬하기3] 자바

나는 Arrays.sort() 시간 초과날까봐 안 썼는데..

Arrays.sort() 쓰셨고, 출력할 때 StringBuilder 써서 출력하셨다.

알 수 없는 시간·메모리 제한의 세계~~😵🤯

 

 

- 풀이2) BufferedWriter  사용

[백준 알고리즘][자바] 10989번 : 수 정렬하기 3

풀이는 비슷한데 출력할 때 결과 출력할 때 BufferedWriter 쓰셨다.

 

 

- 풀이3) 기수 정렬

<기수 정렬>
- 자릿수만 비교
- 시간 복잡도 : O(kn)
- 10개의 큐 이용. (= 값의 자릿수) (일의 자리 → 십의 자리 → 백의 자리 →  ...)
- 시간 복잡도가 가장 짧음. → 정렬해야 할 데이터 개수가 너무 많은 경우 사용

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];

        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }

        radix_sort(A, 5);   // 기수 정렬 함수 수행

        StringBuilder sb = new StringBuilder();
        for(int i : A) {
            sb.append(i + "\n");
        }
        System.out.println(sb);
    }

    public static void radix_sort(int[] A, int max_size) {
        int[] output = new int[A.length];
        int jarisu = 1;
        int cnt = 0;

        // 최대 자리수만큼 반복
        while(cnt != max_size) {
            int[] bucket = new int[10];

            // 일의 자리부터 반복
            for(int i : A) {
                bucket[(i / jarisu) % 10]++;    
            }

            // 합 배열 이용해 idx 계산
            for(int i = 1 ; i < 10 ; i++) {
                bucket[i] += bucket[i - 1];
            }

            // 현재 자릿수 기준 정렬
            for(int i = A.length - 1 ; i >= 0 ; i--) {
                output[bucket[(A[i] / jarisu % 10)] - 1] = A[i];
                bucket[(A[i] / jarisu) % 10]--;
            }

            // 다음 자릿수 이동 위해 현재 자릿수 기준 정렬 데이터 저장
            for(int i = 0 ; i < A.length ; i++) {
                A[i] = output[i];
            }

            jarisu *= 10;   // 자리수 증가
            cnt++;
        }
    }
}

 

---

(참고)

- 풀이

[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]

 

✔ 카운팅 정렬

자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)

 

✔ 기수 정렬

 

기수 정렬(Radix Sort)