목록10989 (1)

팥빵 먹으면서 코딩하는 블로그

04. 카운팅 정렬(counting sort)

응용문제 : 백준 10989 카운팅 정렬(counting sort)란 데이터의 개수를 세어 정렬하는 방법이다. 시간복잡도는 O(N)으로 다른 정렬방법(quick sort, radix sort, etc.)보다 압도적으로 시간이 짧다. 하지만 데이터 값이 큰 경우에는 배열의 메모리 문제가 터질 수 있다는 단점이 있다. (아래 백준 문제의 최대 데이터 값은 10,000이다. 이보단 작은 데이터 값을 최대로 가진 문제에 카운팅 정렬을 쓰는 걸 추천한다.) 직관적으로 카운팅 정렬을 보려면 3개의 array가 필요하다. 1. 정렬되지 않은(정렬해야 할) 데이터를 모은 array 2. (index=데이터 값) / 각 데이터 값(=index)의 개수를 입력한 array 3. 덧셈 처리한 2번 array의 각 값에 -1..
study/JAVA 2023. 9. 9. 22:36
이전 Prev 1 Next 다음