책/Do it! 알고리즘 코딩 테스트 자바 편

Day-7 계수 정렬

댈팽이 2024. 3. 27. 22:56
728x90

1. 계수 정렬

  • 데이터가 몇 번 나왔는지 세어 정렬하는 방식이다.
  • 시간 복잡도가 O(n)으로 매우 빠르다.
  • 수의 범위가 클수록 메모리 낭비가 심하다.

2. 계수 정렬 과정

  1. 각 데이터가 나온 횟수를 count array에 저장한다.
  2. count array의 누적합 배열을 만든다.
  3. 누적합 배열을 이용하여 정렬된 배열을 만든다.

3. 예제 문제

 

[2750] 수 정렬하기 (JAVA)

# 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이

spicyrisotto.tistory.com

728x90