문제이해
이 문제는 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 문제입니다.
입력
입력으로 수의 갯수가 주어지고, 두번째줄부터는 N개의 수가 주어집니다.
이때 수는 절댓값이 1000000보다 작거나 같은 정수이고 수는 중복되지 않습니다.
출력
오름차순으로 정렬한 결과를 한 줄에 하나씩 출력합니다.
문제접근
- 입력을 위해 BufferedReader를 사용했습니다.
- 출력을 위해 StringBuilder를 사용했습니다.
방법1_Collections.sort()
처음에 문제를 잘못 읽어 입력 예시에서 5가 두 번 나온 것을 보고, 중복해서 입력하여도 중복을 제거한 이후에 정렬해서 값을 보여줘야 하는 문제로 이해했습니다.
- HashSet + list + Collections.sort + BufferedReader
문제를 풀기 위해 HashSet, List, Collections.sort() 를 사용해주었는데, 느려도 너~무 느리고, 결과값도 다르게 나오길래 다시 문제를 보니 첫째줄은 입력할 수의 갯수였습니다.
- list +Collections.sort + BufferedReader
그래서 두번째 시도에서는 HashSet을 이용하지 않고, 바로 list에 추가해서 collections.sort()를 사용해주었습니다. 근데 왜인지 더 느려졌습니다....
구글링해보니 다들 나처럼 풀은게 내 코드가 정말 최악의 코드인줄 알았는데 아니더라는 ..
입출력할때 BufferedReader이랑 StringBuilder가 편해서 늘 사용했는데 다른 방법을 이용하면 시간초과가 난다고 합니다.
또한 이 문제는 Arrays.sort()를 이용하면 시간초과가 난답니다.
왜인지 궁금해서 찾아보았습니다.
Collections.sort()
Collections.sort() 은 Timsort으로 합병 및 삽입정렬 알고리즘을 사용합니다.
이렇게 두가지가 섞인 정렬알고리즘을 hybrid sorting algorithm 이라고 합니다.
Collections.sort()를 사용하려면, List계열의 자료구조를 사용해야합니다.
Arrays.sort()
입력값의 범위에 따른 Quick sort의 성능차이
왜 Arrays.sort()를 사용하면 시간초과가 날까요 ?
바로 dual-pivot Quicksort알고리즘을 사용하기 때문입니다.
Dual-pivot Quicksort는 기존의 Quicksort가 하나의 피벗을 사용하여 배열을 두 개의 부분으로 나누는 것과 달리, 두 개의 피벗을 사용하여 배열을 세 개의 부분으로 나눕니다.
- 첫 번째 피벗(pivot1)보다 작은 값
- 두 번째 피벗(pivot2)보다 큰 값
- 두 피벗 사이의 값
퀵소트의 성능은 피벗을 어떻게 선택하느냐에 따라 성능이 크게 달라집니다.
만약, 배열이 이미 정렬되어있어 항상 피벗으로 첫번째나 마지막 요소를 선택하게 된다면 어떻게 될까요 ?
배열이 계속해서 한쪽으로 치우치게 되므로, 퀵소트는 n-1개의 원소를 가진 하위배열로 나누어 지기 때문에 시간복잡도로 worst case인 의 시간복잡도를 가집니다.
입력값의 범위는 피벗을 얼마나 잘 선택하는지에 영향을 미칩니다.
만약 배열이 다음과 같이 입력값의 범위가 넓고 값들이 고르게 분포되어있지 않은 경우, 피벗을 선택할때 배열을 균등하게 나누지 못하고 한쪽으로 치우치게 되어 성능이 저하될 수 있습니다.
피벗을 선택하는 경우에는 배열의 중간값을 선택하고 나머지 피벗은 배열의 끝값을 선택합니다.
만약, 값의 범위가 좁다고 해봅시다.
이 경우, 중간값과 끝값을 피벗으로 선택하면 배열은 균등하게 나누어집니다.
값의 범위가 넓은 경우를 살펴봅시다.
이 경우, 중간 인덱스의 값은 1이고 끝값은 99999999입니다.
피벗을 중간값과 끝값으로 선택하면:
- 중간값 1을 기준으로 나누면, 대부분의 값이 1로 나뉘고, 오른쪽에 극단적인 값 99999999만 남습니다.
- 끝값 99999999를 기준으로 나누면, 99999999보다 작은 모든 값이 한쪽에 몰리게 됩니다.
이렇게 되면, 배열이 균등하게 나누어지지 않고 대부분의 값이 한쪽에 몰리게 되어, 퀵소트의 성능이 으로 떨어집니다.
따라서, 값들이 고르게 분포되지 않으면 비효율적인 분할이 발생할 수 있습니다.
이렇게 일부러 값의 범위를 크게 줘서 흔히 사용하는 방법을 사용하지 못하도록 함정을 파놓은 문제라고 합니다.
방법2_counting sort
서치해서 본 방법중에 빠르고 좋은 방법이 있었습니다.
바로 counting Sort를 이용하는 방법입니다.
- counting Sort
counting Sort는 각 배열원소끼리 직접 비교하는것이 아닌, 인덱스를 가지고 위치를 찾아나가는 방법입니다.
직접 비교하는 정렬이 아니므로 시간복잡도를 으로 하는 매우 빠른 방법이라고 할 수 있습니다.
boolean[]배열에 입력받은 값을 idx로 사용하면 됩니다.
code
- HashSet + list +Collections.sort + BufferedReader
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException{
HashSet<Integer> set = new HashSet<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++) {
set.add(Integer.parseInt(br.readLine()));
}
List<Integer> list = new ArrayList<>(set);
Collections.sort(list);
StringBuilder sb = new StringBuilder();
for(int i=0; i<n; i++) {
sb.append(list.get(i)).append("\n");
}
System.out.println(sb);
}
}- list + Collections.sort + BufferedReader
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<Integer> list = new ArrayList<>();
for(int i=0; i<n; i++) {
list.add(Integer.parseInt(br.readLine()));
}
Collections.sort(list);
StringBuilder sb = new StringBuilder();
for(int i=0; i<n; i++) {
sb.append(list.get(i)).append("\n");
}
System.out.println(sb);
}
}- counting sort + BufferedReader
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
/*
-1000000 ~ 1000000
기준점 0 = index 100000 으로 생각
*/
boolean[] arr = new boolean[2000001];
int N = Integer.parseInt(br.readLine());
for(int i = 0; i < N; i++) {
arr[Integer.parseInt(br.readLine()) + 1000000] = true;
}
for(int i = 0; i < arr.length; i++) {
if(arr[i]) {
sb.append((i - 1000000)).append('\n');
}
}
System.out.print(sb);
}
}