백준 10989번 자바

문제

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

1.기수정렬? 계수정렬?

- 기수정렬(Radix Sort) : 낮은 자리수부터 정렬을 하고 그 배열을 이용해 다음 자리수를 정렬하는 값비교 없이 수행되는 정렬 방법이다. 

 

- 계수정렬(Counting Sort) : 입력 배열의 원소값을 계수하여 새 배열에 누적합으로 담아 정렬하며 기수 정렬과 마찬가지로 값비교없이 수행하는 정렬방법이다.

 

더 큰 키들을 더 효율적으로 처리할 수 있는 다른 정렬 알고리즘인 기수 정렬의 서브루틴에 종종 사용된다. - 위키백과 -

 

- 둘다 값비교 없이 정렬을 수행하기때문에 시간복잡도는 O(N)으로 작다. 하지만 원소 값의 범위가 배열의 길이보다 크거나 음의정수, 부동소수점 등 사용이 제한되는 경우가 많다.

 

2. 일반적인 기수정렬을 이용한 구현(메모리초과로 실패)

- 일반적인 기수정렬 구현 방법으로 길이를 10으로 하는 큐 배열에 원소값을 1의 자리부터 비교해 추가한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main10989 {

	static int N;
	static int[] arr;
	static int placeValue = 1; // 자리값
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		for (int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Queue<Integer>[] qList = new LinkedList[10];
		for (int i=0; i<10; i++) {
			qList[i] = new LinkedList<Integer>();
		}
	
		int temp = 0;
		for (int i=0; i<N; i++) {
			temp = (arr[i]/placeValue)%10;	
			// temp 인덱스로 하는 큐에 본인의 인덱스를 담는다.
			qList[temp].add(i);
			// tempArr이 10으로 나눠져 그 다음 높은 자리수인 상태이다. 예를 들어 101 -> 10
			
		}
		
		for (int k=0; k<5; k++) {
			for (int i=0; i<10; i++) {
				int size = qList[i].size();
				for (int j=0; j<size; j++) {
					// 0번째 큐부터 값을 poll한 인덱스를 tempArr에 전해줘 10으로 나눈 나머지를 구한다.
					temp = (arr[qList[i].peek()]/placeValue)%10;
					qList[temp].add(qList[i].poll());
				}
			}
			placeValue *= 10;
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i=0; i<10; i++) {
			while (!qList[i].isEmpty()) {
				sb.append(arr[qList[i].poll()] +"\n");
			}
		}
		
		System.out.println(sb);
	}
}

 

3. 계수정렬을 활용한 구현

- 원소값의 범위가 10000이하의 자연수이기때문에 countingArr의 길이가 10001이 된다. 여기선 굳이 누적합을 계산하지 않아도 되기에 단순 계수만으로 해결이 가능하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main10989 {

	static int N;
	static int[] arr;
	static int[] countingArr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		countingArr = new int[10001];
		for (int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		for (int i=0; i<N; i++) {
			countingArr[arr[i]]++;
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i=1; i<countingArr.length; i++) {
			while (countingArr[i] != 0) {
				sb.append(i + "\n");
				countingArr[i]--;
			}
		}
		System.out.println(sb);
	}
}

 

4. 계수정렬을 활용한 기수정렬 구현

- 계수정렬처럼 각 값을 누적합으로 계산해 정렬을 한다. 이때 기수정렬 방식을 사용해 1의 자리부터 가장 큰 값의 자리수까지 해당 과정을 반복한다.

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++;
    }
  };
}
// 출처 https://github.com/doitcodingtestjava/answer/blob/main/%EC%A0%95%EB%A0%AC/P10989_%EC%88%98%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B03.java

 

정리 : 기수, 계수정렬은 특별한 조건에서만 활용이 가능하다는 점을 잊지말자.

- 양의정수

- 원소 최대값의 자리수가 작을경우

- 배열길이 N이 원소값의 범위보다 클 경우