이런저런 문제들 #2750: 수 정렬하기 [JAVA]

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

 

---

 

 

 

문제 접근

 

 

 

 

 

1. 선택 정렬

 

 

- 장점 : 구현하기 쉬움.

 

- 단점 : 시간복잡도 O(n2)으로 성능 좋지 않음.

 

 

 

 

 

 

2. Arrays.sort()

 

 

- dual-pivot Quicksort 알고리즘 사용

- 평균: O(nlogn), 최악의 경우: O(n2) -> 백준에서 최악의 경우 노린 데이터를 입력으로 줌.

 

 

 

 

 

 

3. counting sort (카운팅 정렬, 계수 정렬) [  https://st-lab.tistory.com/104  ]

 

 

- 값을 비교하면서 정렬하는 것이 아니라, 입력받은 값을 index 으로 하여 해당 값의 출현 빈도수를 체크

 

- 시간복잡도가 O(n)으로 매우 빠른 알고리즘.

 

- 만약 입력되는 수의 개수는 적지만, 수의 범위가 매우 클 경우 심한 메모리 낭비와 더불어

  자바에서는 1차원 배열 객체 하나의 크기는 최대 Integer.MAX_VALUE 미만으로만 가능하기 때문에 (배열의 경우 int값으로 색인하며  또한 대부분의 사용자의 heap 메모리가 하나의 배열을 8GB 만큼 큰 메모리를 확보하지 못한다.)

  실생활에서는 거의 안쓰인다.

  그렇기 때문에 대부분 언어에서는 TimSort나 QuickSort 를 쓰는 것이다.

 

 

 

 

 

 

 

3-1. counting sort 응용ver. 

 

 

- 입력값의 범위를 알 때 사용 가능.

 

- 입출력만 하는 경우 사용 가능.

 

- 백준 문제 풀 때 추천.

 

 

 

 

 

 

 

 

 

 

 

▲ 참고

 

 

출력 시 StringBuilder를 사용해서 속도를 높이자.