728x90
일반적인 풀이방법 --> 시간 초과가 발생한다.
아래 더보기를 통해 이유와 코드 확인하기.
더보기
내장 함수를 사용하라고 문제에 나와있지만
Arrays.sort()를 쓰면 시간초과가 발생한다.
이유는 Arrays.sort()는 dual-pivot 퀵 정렬을 사용하기 때문이다.
이 알고리즘은 최악의 경우 시간복잡도가 O(n^2)인 알고리즘이기 때문에 시간초과가 발생할 가능성이
높아지는 것이다.
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] arr = new int[N];
for(int i=0; i<N ; i++){
arr[i]=sc.nextInt();
}
Arrays.sort(arr);
for(int i=0; i<N ; i++){
System.out.println(arr[i]);
}
}
}
시간 초과를 방지하기 위해
TimeSort (합병 및 삽입정렬) 알고리즘을 사용하는 Collenctions.sort()를 사용할 것이다.
위 알고리즘은 O(n) ~ O(nlogn)의 시간복잡도를 보장하는 강력한 정렬 알고리즘이다.
위 함수를 사용할 때 주의할 점은 일반적인 배열을 사용하면 안되고
ArrayList나 LinkedList와 같은 자료구조를 사용해야 동작한다.
Scanner로 그냥 받아서 사용할 때도 시간초과가 나므로
StringBuilder를 이용해서 문제를 해결하였다.
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int N = sc.nextInt();
ArrayList<Integer> list = new ArrayList<>();
for(int i=0; i<N ; i++){
list.add(sc.nextInt());
}
Collections.sort(list);
for(int value : list){
sb.append(value).append('\n');
}
System.out.println(sb);
}
}
728x90
'백준 단계별' 카테고리의 다른 글
[Java] 백준 2108: 통계학 (0) | 2023.02.14 |
---|---|
[Java] 백준 10989: 수 정렬하기 3 (0) | 2023.02.14 |
[Java] 백준 25305: 커트라인 (0) | 2023.02.02 |
[Java] 백준 2587: 대표값2 (0) | 2023.02.02 |
[Java] 백준 2750: 수 정렬하기 (0) | 2023.02.02 |