counting sort2 [Java/백준/정렬] 2751 - 수 정렬하기 2 문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 시행착오 1 시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있다길래, 병합정렬로 풀려고 했는데 시간초과가 생겼다. 아래 코드와 비슷한거 같은데 왜 시간이 더 걸리는 걸까ㅠ import java.util.Scanner; public class Main { private static void mergeSort(int[] arr) { int[] tmp = new int[ar.. 2020. 8. 20. [자료구조/C, Java] 계수 정렬(Counting Sort) https://www.youtube.com/watch?v=n4kbFRn2z9M 목소리가 특이하신 분...ㅎ 범위 조건이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있다. 계수 정렬(Counting Sort)는 단순하게 '크기를 기준으로 개수를 세는' 알고리즘이다. 지금까지는 모든 데이터를 그 자체로 위치를 바꾸어가며 정렬하는 알고리즘이었다. 계수 정렬은 '크기를 기준'으로 갯수만 세주면 되기 때문에 위치를 바꿀 필요가 없다. 모든 데이터에 한 번씩만 접근하면 된다는 점에서 무척이나 효율적이다. 1. 결과 배열의 크기를 숫자의 크기 범위만큼 잡아준다. 2. 하나를 확인할 때마다 배열에 데이터를 한개씩 증가시켜준다. 3. 출력할 때는 단순하게 배열 원소의 숫자만큼 반복하면 된다. - 시간 복잡도 : O(N).. 2020. 8. 20. 이전 1 다음