문제
교재 풀이
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class P10989_수정렬하기3 {
public static int[] A;
public static long result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(br.readLine());
}
br.close();
Radix_Sort(A, 5);
for (int i = 0; i < N; i++) {
bw.write(A[i] + "\n");
}
bw.flush();
bw.close();
}
public static void Radix_Sort(int[] A, int max_size) {
int[] output = new int[A.length];
int jarisu = 1;
int count = 0;
while (count != max_size) // 최대 자리수 만큼 반복
{
int[] bucket = new int[10];
for (int i = 0; i < A.length; i++) {
bucket[(A[i] / jarisu) % 10]++; // 일의 자리 부터 시작
}
for (int i = 1; i < 10; i++) { // 합배열을 이용하여 index 계산
bucket[i] += bucket[i - 1];
}
for (int i = A.length - 1; i >= 0; i--) { // 현재 자리수 기준으로 정렬하기
output[bucket[(A[i] / jarisu % 10)] - 1] = A[i];
bucket[(A[i] / jarisu) % 10]--;
}
for (int i = 0; i < A.length; i++) {
A[i] = output[i]; // 다음 자리 수 이동을 위해 현재 자리수 기준 정렬 데이터 저장
}
jarisu = jarisu * 10; // 자리수 증가
count++;
}
};
}
내 풀이) 24.6.11에 풀고 에러나고 틀림
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args) throws IOException{
// 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다.
// 둘째 줄부터 N개의 줄에는 수가 주어진다.
// 이 수는 10,000보다 작거나 같은 자연수이다.
// N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력
// 접근법
// 일단 내 목적은 코테 개념, 기수 정렬을 구현해서 적용하는 것이다
// 한 줄에 하나씩 출력해라인가. BufferedWriter나 StringBuffer인데
// 기수 정렬은 어떻게 하는가
// 일단 구간합을 이용해 구현한다는 건 훑어서 안다
// 큐를 10개 사용해라는데, 이는 잘 모르겠고
// 일의 자리부터 기준으로 정렬하고 그렇게 쭉쭉 나아가는 형식
// 큐에 입력할 때 수 앞자리를 0으로 채워야 할 경우도 있음
// 슈도코드
// scanner로 n 입력받음
// int[] a를 선언
// for n번 반복해서
// a에 다 입력해준다
// output 배열: 결과 출력용 배열
// jarisu 변수: 현재 기준인 자릿수를 표현 -> 1, 10, 100, 1000으로 10배씩 됨
// 기수 정렬을 한다
// 구간 합? 어떤 배열을 구간합? 그러니까
// a 배열에 대해 일의 자리를 기준으로 카운트해줌
// 즉 일의 자리가 1이면 인덱스 1에, 0이면 0에 카운트 해줌
// 카운트한 배열을 구간 합으로 만듦
// 반복문을 돌면서
// output 배열에 현재 자릿수 기준으로 오름차순한 결과를 넣는다
// 넣을 땐 예를 들어 자릿수 기준이 10의 자리고,
// 3을 넣을 땐 03으로 취급해서 넣어야 하는데
// 이를 어떻게 구현하지?
// 문자열로 앞에 0을 4자리가 되게 붙여서 저장하고
// 꺼내서 기준 자릿수가 무엇인지 카운트할 때
// 다시 문자열에서 숫자로 바꾼 다음
// 조건문을 이용해서 '0'인지, '1'인지 뭐 이런 식으로 비교해서
// 다른 방법
// if문 이용해서 현재 원소가 <10일 땐 혹은 <100일 땐 0으로 취급
// 한다는 식으로 하면 되지
// 즉 현재 원소 <jarisu를 비교해서 하면 되지 않을까?
// 자릿수를 하나 ++하고 다시 반복한다.
// 반복은 4번까지 진행한다.
// 최적화하는 코드는 나중에 미뤄두고, 일단 되기만 하면 되니까
// buffer(즉 정답)을 출력한다
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] a=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
int[] output=new int[n];
int[] cnt=new int[n];
int jarisu=1; // 일의 자리부터 시작
while(jarisu<=1000){
// cnt 배열을 구간합으로 만드는 과정
for(int i=0;i<n;i++){
// 3445 / 10은 344고 344%10은 4가 되고
cnt[(a[i]/jarisu)%10]++;
}
for(int i=1;i<n;i++){
cnt[i]+=cnt[i-1];
}
//output 배열에 jarisu 기준 오름차순 저장하기
for(int i=0;i<n;i++){
output[cnt[(a[i]/jarisu)%10]]=a[i];
cnt[(a[i]/jarisu)%10]--;
// cnt의 구간합의 의미가
// cnt[3]이 5란 뜻이, 자릿수 기준 0~3인 숫자 개수가 5개 있다는 소리고
// output[5]에 하나 넣고 cnt[3]--하면
// 그 다음부턴 cnt[3]에 해당하는 게 output[4]에 저장되고 뭐 이런 식이었던 거 같은데
// 이 이상은 생각 안 나니 일단 무작정 코드 만들어 봐야 겠다
}
// for문 세 개의 일련의 흐름을 4번까지 반복함
jarisu*=10;
}
for(int i:output){
System.out.println(i);
}
}
}
// 디버그
// 왜 인덱스 범위가 늘어나지
// 인덱스 10이라고. 어떻게 output[cnt[(a[i]/jarisu)%10]]=a[i];에서 cnt[(a[i]/jarisu)%10]
// 게 10이 나온다고 ? 예제 입력인데
// 물론 합 배열로 바꾸면서 10을 넘을 수 있음
// 예로 11이면...
// 시간 오버...
설명
6.11에 푼 건 딱 코드 짜고 돌렸을 때 인덱스 범위 에러 뜨고 끝이었음.
디버그 하려 했지만, 1시간 제한을 넘었기 때문에 포기하고 정답 코드 봄
- output[bucket[(A[i] / jarisu) % 10] - 1]에서 -1을 하는 이유?
- Radix Sort와 Counting Sort
Radix Sort는 자릿수별로 정렬하는 알고리즘입니다. 각 자릿수별로 정렬하기 위해 Counting Sort를 사용합니다. Counting Sort에서 각 자릿수의 발생 빈도를 계산한 후, 각 숫자가 정렬된 배열에서 어디에 위치할지를 계산하는 합배열을 생성합니다.
- Counting Sort의 합배열: Counting Sort의 과정은 다음과 같습니다
- 버킷 카운트: 각 자릿수의 발생 빈도를 세어 버킷에 저장합니다.
버킷: [0, 2, 2, 2, 1, 2, 0, 1, 0, 0] - 합배열 계산: 합배열을 계산하여 각 숫자가 정렬된 배열에서 어디에 위치할지를 결정합니다.
합배열: [0, 2, 4, 6, 7, 9, 9, 10, 10, 10]
- 합배열의 의미
합배열의 값은 해당 숫자가 정렬된 배열에서 마지막으로 등장하는 위치의 다음 인덱스를 나타냅니다. 예를 들어, 합배열의 값이 4인 경우, 해당 숫자는 정렬된 배열의 인덱스 3(0부터 시작)까지 차지합니다.
- 인덱스 조정
배열의 인덱스는 0부터 시작합니다. 따라서 합배열에서 얻은 위치 값을 그대로 사용하면 실제로 배열의 범위를 초과하게 됩니다. 이를 조정하기 위해 -1을 합니다.
- 예시로 설명
예를 들어, bucket[(A[i] / jarisu) % 10]의 값이 4인 경우, 이 값은 숫자가 정렬된 배열의 4번째 위치(인덱스 4)까지 포함된다는 의미입니다. 하지만 배열 인덱스는 0부터 시작하기 때문에 실제로는 인덱스 3에 해당하는 위치가 됩니다. 따라서 -1을 하여 정확한 인덱스를 얻습니다.
- 코드 분석
java코드 복사
for (int i = A.length - 1; i >= 0; i--) { // 현재 자리수 기준으로 정렬하기
output[bucket[(A[i] / jarisu) % 10] - 1] = A[i];
bucket[(A[i] / jarisu) % 10]--;
}
- bucket[(A[i] / jarisu) % 10]은 해당 숫자가 정렬된 배열에서 마지막으로 등장하는 위치의 다음 인덱스를 가리킵니다.
- 1을 하여 정확한 배열 인덱스를 얻습니다.
- output[bucket[(A[i] / jarisu) % 10] - 1] = A[i]는 정렬된 배열의 올바른 위치에 숫자를 배치합니다.
- bucket[(A[i] / jarisu) % 10]--는 다음 동일한 숫자의 위치를 위해 버킷 값을 감소시킵니다.
- 요약
output[bucket[(A[i] / jarisu) % 10] - 1]에서 -1을 하는 이유는 합배열의 값이 정렬된 배열의 마지막 위치의 다음 인덱스를 나타내기 때문에, 이를 0부터 시작하는 배열 인덱스에 맞추기 위해 -1을 하는 것입니다. 이는 Counting Sort의 중요한 부분이며, Radix Sort의 각 단계에서 올바른 정렬을 보장합니다.
'CODING TEST > BOJ' 카테고리의 다른 글
| [java] 문제 024 (백준 2023) (0) | 2024.06.12 |
|---|---|
| [java] 문제 023 (백준 11724) (0) | 2024.06.12 |
| [java] 문제 021 (백준 1517) (0) | 2024.06.11 |
| [java] 문제 020 (백준 2751) (0) | 2024.06.10 |
| [java] 문제 019 (백준 11004) (0) | 2024.06.10 |