counting 정렬과 [백준] 11650번

 

counting 정렬은 일정 상황에서 O(n+k)성능을 가지는 정렬이다.

일정 상황이란 배열의 min과 max를 알 수 있을 때 쓰인다. 

https://www.youtube.com/watch?v=Urmb0FpW6Hk

개념은 이 유튜브를 참고하였다. 개념을 쉽고 잘 설명해주었다. 

구현을 위해서는 총 4단계가 필요하다.

1. 나타나는 값의 개수 세기 

2. 누적합으로 배열 배꾸기 

3. 누적합 배열에서 -1

4. 입력받은 배열 뒤에서부터 선회하며 결과값 자리 정하기 (이후 누적합 배열 -1 필요)

다음은 정확이 그대로 나타낸 코드이다(0부터 10까지 범위)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args)  {
		/// 0부터 10까지의 자연수 
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int count[] = new int[10];
		int arr[] = new int[a];
		int result[] = new int[a];
		for(int i=0;i<a;i++) {
			int b = sc.nextInt();
			arr[i] = b;
			count[b]++;
		}
		for(int i=1;i<10;i++) {
			count[i] = count[i]+count[i-1];
		}
		for(int i=0;i<10;i++) {
			count[i]--;
		}
		for(int i=a-1;i>=0;i--) {
			result[count[arr[i]]] = arr[i];
			count[arr[i]]--;
			//System.out.println(Arrays.toString(count));
		}
		System.out.println(Arrays.toString(result));
	}
	
}

출력결과는 !!!

카운팅 정렬을 활용한 백준 문제 11650을 풀어보겠다.

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

10989번: 수 정렬하기 3

이 문제에서는 배열을 결과값으로 안뱉어 낸다는 장점이 있다. 그렇다면 ? 누적합을 안하고 단순히 입력값을 출력해주기만 하면 된다.

따라서 나타나는 해당 원소에 해당하는 배열을 하나씩 올리고 

출력할때는 해당 배열의 크기만큼 반복해서 출력하면 된다는 뜻이다.

 설명을 잘 못했는데 코드를 이해하면 쉽다 .

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;



public class Main {

	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 a = Integer.parseInt(br.readLine());
		int count[] = new int[10001];
		for(int i=0;i<a;i++) {
			count[Integer.parseInt(br.readLine())]++;
		}
		for(int i=0;i<10001;i++) {
			while(count[i]>0) {
				bw.append(i+"\n");
				count[i]--;
			}
		}
		bw.close();
	}
	
}

이전에 코드보다 깔끔해졌다. 

 

카운팅 정렬이 자주 쓰이진 않을 듯 하지만 개념을 익혀두자 !