[백준알고리즘] 10989번 수 정렬하기 3 - 계수(카운팅) 정렬 [Counting Sort] 로 풀어보자 [Java - 자바]

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하ㅣ오.

 

입력

첫째 줄에 수의 개수 N(1 <= N <= 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

 

 

코드

1) 백준알고리즘 문제에 맞춤 풀이

package com.company.sort;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class arrangeTheNumber_countingSort4 {
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        int[] count = new int[10001];
 
        for (int i = 0; i < N; i++) {
            count[Integer.parseInt(br.readLine())]++;
        }
 
        br.close();
 
        StringBuilder sb = new StringBuilder();
 
        for (int i = 0; i < 10001; i++) {
            while (count[i] > 0) {
                    sb.append(i).append('\n');
                    count[i]--;
            }
        }
            System.out.println(sb);
    }
}
 

 

 

 

2) count배열을 동적으로 할당 받을 수 있는 풀이

package com.company.sort;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class arrangeTheNumber_countingSort {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int NUMBER_RANGE = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
 
        int[] count = new int[NUMBER_RANGE];
        int[] arr = new int[N];
 
        // 7개의 배열을 모두 0으로 초기화
        for (int i = 0; i < NUMBER_RANGE; i++) {
            count[i] = 0;
        }
 
        // N의 크기만큼 숫자 입력
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        // count[0] ~ count[7] 값을 카운팅
        for (int i = 0; i < N; i++) {
            count[arr[i] - 1]++;
        }
 
        for (int i = 0; i < NUMBER_RANGE; i++) {
            if (count[i] != 0) {
                for (int j = 0; j < count[i]; j++) {
                    System.out.print((i + 1) + " ");
                }
            }
        }
    }
}

 

 

 

 

 

 

 

 

베타존 : 네이버쇼핑 스마트스토어