[ 문제 ]
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
[ 입력 ]
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
[ 출력 ]
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
[ 풀이 ]
0. BufferedReader, StringBuilder 생성
1. N 입력받기
2. 카운팅 정렬
3. 출력
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
// 0
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 1
int N = Integer.parseInt(br.readLine());
// 2
int [] arr = new int [10001]; // 수의 범위는 1 ~ 10000
for(int i = 0; i < N; i++) { // 수의 개수 만큼 반복
int num = Integer.parseInt(br.readLine());
arr[num]++;
}
// 3
for(int i = 0; i < arr.length; i++) {
while(arr[i]-- > 0) {
sb.append(i).append("\n");
}
}
System.out.println(sb);
}
}[ 배운 것 ] - 카운팅 정렬
-
사용 조건
-
데이터의 크기 범위가 제한 (ex. 0~100까지의 수)
-
데이터가 양의 정수
-
가장 큰 데이터와 가장 작은 데이터의 차이가 백만을 넘기지 않음
-
- 알고리즘
1) counting 배열을 모두 0으로 초기화
2) 앞에서부터 입력에서 각각의 값이 발생한 횟수를 카운트 (A배열)
3) 앞에서부터 누적합 구하기 (C배열)
4) A배열의 뒤에서부터 해당 값 -> C배열의 값 -> B배열의 인덱스
[ 실행 결과 ]
