[백준]2750 수 정렬하기 2 - 자바/Java

10989번: 수 정렬하기 3

🌱풀이

알고리즘

1. 기수 정렬을 이용한 알고리즘이다.
2. radixSort(A,5)에서 radixSort는 기수 정렬을 의미하고, A는 배열, 5는 최대 자릿수다.
3. 이해 안됨.. 쉬었다하자.

메모리 : 336892KB, 시간 : 2732ms

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static int[] A;
	static long result;
	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());
		A = new int[N];
		for(int i = 0; i<N; i++) A[i] = Integer.parseInt(br.readLine());
		br.close();
		radixSort(A,5);
		for(int i = 0; i<N; i++) bw.write(A[i]+"\\n");
		bw.flush();
		bw.close();
	}
	public static void radixSort(int[] A, int max_size) {
		int[] output = new int[A.length];
		int J = 1; //자리수
		int count = 0;
		while(count != max_size) {
			int[] bucket = new int[10];
			for(int i = 0; i<A.length; i++) {
				bucket[(A[i]/J)%10]++; //해당 자리수의 개수
			}
			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]/J%10)]-1] = A[i];
				bucket[(A[i]/J)%10]--;
			}
			for(int i = 0; i<A.length; i++) {
				A[i] = output[i];
			}
			J = J*10;
			count++;
		}
	}
}

---

🪴코드 리뷰

이것도 예전에 풀어놨던 코드다. 아무래도 복잡한 알고리즘을 직접 구현할 능력은 없으니 이렇게 꼼수로라도 푼 것 같다. 정수형 배열의 길이를 입력될 수 있는 최대 수 만큼 선언해놓고, 입력되는 값을 인덱스삼아 값을 늘려준다. 배열에 1 이상의 값이 입력되어 있으면 해당 인덱스가 입력된 것이다.

출력할 때는 0번 인덱스부터 돌면서 값이 0 이 아닌 모든 인덱스를 출력하되, 그 값만큼 출력해주면 된다. 한 번 입력이 끝나면 바로 정렬된 형태로 출력이 가능하다는게 최대 장점인듯하다.

🌿메모리 : 480552KB, 시간 : 1660ms

💡 풀이자 : 본인

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder(); 
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[10001];
		while(N-->0) {
			arr[Integer.parseInt(br.readLine())]++;
		}
		for(int i = 0; i<arr.length; i++) {
			if(arr[i] != 0) {
				for(int j = 0; j<arr[i]; j++) {
					sb.append(i).append("\\n");
				}
			}
		}
	System.out.println(sb.toString());	
	}
}

---

다들 간단하게 풀었네? Array 라이브러리가 제공하는 정렬 알고리즘을 사용했다.

🌿메모리 : 363800KB, 시간 : 2420ms

💡 풀이자 : sag1025

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());

        int[] number = new int[N];

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

        Arrays.sort(number);
        for (int i : number) {
            sb.append(i);
            sb.append("\\n");
        }
        System.out.println(sb);
    }

}

---

Conclusion

• 괜히 어렵게 푼 것 같지만 기수 정렬을 연습한 셈 치자.
• 과거의 나는 잔머리가 아주 좋았던 걸로.