책/Do it! 알고리즘 코딩 테스트 자바 편
Day-7 기수 정렬
댈팽이
2024. 3. 27. 20:26
728x90
1. 기수 정렬
- 값을 비교하지 않는다.
- 데이터의 자릿수를 비교해 정렬하는 방식이다.
- 시간 복잡도는 O(kn)이다. k는 데이터의 자릿수이다.
- 시간 복잡도가 가장 짧은 정렬로 데이터의 개수가 많을 때 좋다.
2. 기수 정렬 과정
기수 정렬은 10개의 큐를 이용한다. 각 큐는 값의 자릿수를 대표한다.
일의 자릿수를 기준으로 데이터를 큐에 넣는다.
그 다음 0번째 큐부터 9번째 큐까지 pop한다.
위 과정을 마지막 자릿수까지 반복한다.
3. 예제 문제
[10989] 수 정렬하기 3 (JAVA)
# 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다.
spicyrisotto.tistory.com
[2750] 수 정렬하기 (JAVA)
# 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이
spicyrisotto.tistory.com
728x90