백준 10989 수 정렬하기 3
•
이전의 수 정렬하기 2 보다 수의 범위가 더 커져버렸다. 🫣 그래서 또 다른 정렬을 찾아야 한다.
•
이때의 시간 복잡도는 O(N) 을 만족해야 한다.
계수 정렬
•
계수 정렬은 데이터 값을 직접 비교하지 않고, 단순하게 숫자의 개수를 세어 저장한 후에 정렬하는 알고리즘이다.
◦
때문에 위치를 변경할 필요가 없다.
•
값 비교가 일어나지 않기 때문에 속도가 빠르지만, 개수를 저장하기 위한 추가 공간이 필요하다.
◦
때문에 수의 범위가 작을 수록 유리하다.
•
이때 계산은 끝에서 부터 한다.
◦
값이 중복될 수도 있기 때문이다.
구현 순서
•
리스트를 생성한다.
◦
입력값을 받는 리스트
◦
수위 범위만큼의 리스트
◦
정렬된 수를 담을 리스트
•
입력값을 받는 리스트의 value 를 index 로 하여 counting 배열의 값을 증가시킨다.
•
counting 배열의 누적합을 수행한다.
•
끝에서부터 순회하며, i 번째 원소를 인덱스로 하는 counting 배열을 1 감소 시킨다.
•
이 감소시킨 배열의 값을 인덱스로 하여 결과 리스트에 값을 저장한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
/**
* 수 정렬하기
* @Variable N : 정렬할 수의 개수
*/
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static int[] numbers;
static int[] countings;
static int[] result;
public static void main (String[] args) throws IOException {
int N = Integer.parseInt(br.readLine());
numbers = new int[N];
countings = new int[10000000];
result = new int[N];
for (int i = 0; i < N; i ++) {
numbers[i] = Integer.parseInt(br.readLine());
}
countingNumbers();
cumulativeCountings();
solve();
for (int number : result) {
sb.append(number).append("\n");
}
System.out.println(sb.toString());
}
public static void countingNumbers() {
for (int number : numbers) {
countings[number]++;
}
}
public static void cumulativeCountings() {
for (int i = 1; i < countings.length; i++) {
countings[i] += countings[i - 1];
}
}
public static void solve() {
for (int i = numbers.length - 1; i >= 0; i --) {
int index = numbers[i];
countings[index]--;
result[countings[index]] = index;
}
}
}
Java
복사