import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(bf.readLine());
int[] arr = new int[num];
for (int i = 0; i<num; i++) {
arr[i] = Integer.parseInt(bf.readLine());
}
int temp = 0; // 1. 선택정렬 시간복잡도 n 제곱
for (int i = 0; i<num - 1; i++) {
for (int j = i+1; j< num; j++) {
if (arr[i] > arr[j]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
for (int N : arr) {
System.out.println(N);
}
}
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(bf.readLine());
int[] arr = new int[num];
for (int i = 0; i<num; i++) {
arr[i] = Integer.parseInt(bf.readLine());
}
Arrays.sort(arr); //2. O(nlogn) 최악은 n 제곱
for (int N : arr) {
System.out.println(N);
}
}
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(bf.readLine());
int[] arr = new int[num];
int max = 0;
for (int i = 0; i<num; i++) {
arr[i] = Integer.parseInt(bf.readLine());
if (arr[i] > max) {
max = arr[i];
}
}
int[] counting = new int[max+1];
int[] result = new int[num];
// counting 배열 만들어주기
for (int i = 0; i<num; i++) {
counting[arr[i]]++;
}
// 누적합으로 counting 배열 채워주기
for (int i = 1; i<max+1; i++) {
counting[i] += counting[i-1];
}
// result 배열 채워주기
for (int i = num-1; i>=0; i--) {
counting[arr[i]]--;
result[counting[arr[i]]] = arr[i];
}
for (int N : result) {
if (N != 0) {
System.out.println(N);
}
}
}
}
오름차순으로 정렬하는데에는 여러가지 방법이 있다. 그 도중에 시간복잡도와 상황을 고려해서 가장 유리한 방법으로 풀어야 한다.
이번 문제에서는 매번 배열을 모두 돌며 max값을 도출하는 선택정렬과 자바 Array에서 지원하는 Arrays.sort(arr); 방법으로 풀었고 성능은 아래와 같다.
아래 = 선택정렬
위 = Arrays.sort(arr);