![백준_10989 수 정렬하기3 (기수정렬) - 성공(풀이 참고)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FOgyDx%2FbtsDARxWmI8%2FDZ7WLgJyTHZZaR7Mt66PGK%2Fimg.png)
![kjyyjk](https://t1.daumcdn.net/tistory_admin/static/manage/images/r3/default_L.png)
백준_10989 수 정렬하기3 (기수정렬) - 성공(풀이 참고)Algorithm/Algorithm 문제2024. 1. 18. 13:12
Table of Contents
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BJ_10989 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int i, n;
n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for(i=0; i<n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
radixSort(arr, 5);
StringBuilder sb = new StringBuilder();
for(i=0; i<n; i++) {
sb.append(arr[i]).append('\n');
}
System.out.println(sb);
}
static void radixSort(int[] arr, int max) {
int i, j, k;
int[] output = new int[arr.length];
int[] bucket;
k=1;
for(i=0; i<max; i++) { //각 자릿수
bucket = new int[10]; //각 자릿수의 분포(0~9)를 담을 bucket
for(j=0; j<arr.length; j++) {
bucket[(arr[j]/k)%10]++; //각 자릿수 분포 담기
}
for(j=1; j<10; j++) {
bucket[j] += bucket[j-1]; //bucket을 구간합배열로
}
for(j=arr.length-1 ; j>=0; j--) { //뒤에서부터. 10의 자리부터는 앞 자리들을 기준으로 오름차순 되어있기 때문
output[bucket[(arr[j]/k)%10]-1] = arr[j]; //bucket의 해당 자릿수 값이 n이면, 그 수는 n번째수. 인덱스로는 n-1.
bucket[(arr[j]/k)%10]--; //자릿수의 값이 같은 다른 수를 고려하여 -1. 해당 자릿수가 같아도 앞자릿수가 더 큰 수가 먼저 뒤로 들어감
}
for(j=0; j<arr.length; j++) {
arr[j] = output[j];
}
k*=10; //자릿수 증가
}
}
}
전혀 생각지도 못했던 방식이다
배열 3개만 사용하니 메모리 통과.
당장은 이해했는데 다른 문제를 보고 비슷한 방식을 떠올릴 수 있을지는..
이런게 쌓이다보면 요령도 늘겠지라는 생각
10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
'Algorithm > Algorithm 문제' 카테고리의 다른 글
백준_2023 신기한 소수 (DFS) (0) | 2024.01.20 |
---|---|
백준_11724 연결요소의 개수 (DFS) (0) | 2024.01.19 |
백준_10989 수 정렬하기 3 (기수 정렬) - 실패(메모리초과) (0) | 2024.01.18 |
백준_1517 버블 소트 (병합정렬) (0) | 2024.01.17 |
백준_2751 수 정렬하기2 (풀이 참고 코드개선) (0) | 2024.01.17 |
![kjyyjk](https://t1.daumcdn.net/tistory_admin/static/manage/images/r3/default_L.png)
@kjyyjk :: 녕의 학습 기록
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!