'Do it 자료구조와 함께 배우는 알고리즘 입문' 도서를 토대로 공부하고 관련한 문제를 찾아풀어보고 있습니다.
'도수 정렬' 알고리즘 문제 풀이입니다!!!
문제
https://www.acmicpc.net/problem/10989
[나의 풀이1]
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 [] countingSort(int [] arr, int N, int max){
// 누적도수
int [] f = new int[max+1];
// 작업용 목표 배열
int [] b = new int[N+1];
// 도수분포표
for (int i=0; i<N; i++) f[arr[i]]++;
// 누적도수분포표
for (int i=1;i<=max;i++){
f[i] += f[i-1];
}
// 목표 배열
for (int i=N-1;i>=0;i--){
// * -- 연산자 : 참조한 객체의 값을 -1함
b[--f[arr[i]]] = arr[i];
}
//최종 배열
for (int i=0;i<N;i++) arr[i] = b[i];
return arr;
}
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;
N = Integer.parseInt(br.readLine());
int [] arr = new int [N];
for (int i=0;i<N;i++){
arr[i] = Integer.parseInt(br.readLine());
}
// 최댓값 구하기
int max = arr[0];
for (int i=1; i<N;i++)
if (arr[i] > max) max =arr[i];
arr = countingSort(arr,N,max);
for (int i=0;i<N;i++){
bw.write(arr[i]+"\n");
}
bw.flush();
}
}
[나의 풀이2]
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 [] countingSort(int [] arr, int N, int max){
// 누적도수
int [] f = new int[max+1];
// 작업용 목표 배열
int [] b = new int[N];
// 도수분포표
for (int i=0; i<N; i++) f[arr[i]]++;
// 누적도수분포표
for (int i=1;i<=max;i++){
f[i] += f[i-1];
}
// 목표 배열
for (int i=N-1;i>=0;i--){
// * -- 연산자 : 참조한 객체의 값을 -1함
// max = 7
b[(N-1)-(--f[arr[i]])] = arr[i];
}
//최종 배열
for (int i=0;i<N;i++) arr[i] = b[i];
return arr;
}
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;
N = Integer.parseInt(br.readLine());
int [] arr = new int [N];
for (int i=0;i<N;i++){
arr[i] = Integer.parseInt(br.readLine());
}
// 최댓값 구하기
int max = arr[0];
for (int i=1; i<N;i++)
if (arr[i] > max) max =arr[i];
arr = countingSort(arr,N,max);
for (int i=0;i<N;i++){
bw.write(arr[i]+"\n");
}
bw.flush();
}
}
도수 정렬은 요소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘입니다. 순서대로 도수분포표 만들기, 누적도수분포표 만들기, 목표 배열 만들기, 배열 복사하기 단계로 이루어집니다.👨🌾👨🌾👨🌾
도수 정렬 알고리즘은 중첩for문을 사용하지 않아 효율적인 알고리즘이지만 도수분포표가 필요하기 때문에 전체 데이터의 최솟값, 최댓값을 알고 있어야 사용할 수 있다는 장단점이 있습니다.🏄🏄🏄
문제에서 요구하는 오름차순 정렬을 먼저 구현한 뒤, 반대로 내림차순으로 정렬하는 알고리즘으로 다시 구현해보았습니다.
감사합니다!!!🍉🍉🍉