[ 백준 ] 10989번 수 정렬하기3 / [ Java 이용 ]

 

 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int N = Integer.parseInt(br.readLine());
        int[] cnt = new int[10001]; // 이렇게 한 이유는 N 의 범위가 0에서 시작되는 것이 아니라 1에서 시작되기 때문
        for (int i = 0; i < N; i++) {
            int T = Integer.parseInt(br.readLine());
            // 저장 완료
//            arr[i] = T;
            // 보통은 위처럼 저장하겠지만 그게 아니라 아래처럼!
            cnt[T]++;
        }
        // Arrays 의 sort 로 이용할 경우 시간 복잡도 오류
        //  평균 시간복잡도가 O(nlogn) 이지만 최악의 경우 시간 복잡도 O(n2)
        // ( 추가) Collections 의 경우에도 메모리와 시간이 초과되므로 불가
 
        for(int i=1; i<10001; i++) {
            while (cnt[i]>0) {
                sb.append(i).append('\n');
                //중복 방지
                cnt[i]--;
            }
 
        }
        System.out.println(sb);
    }
}
 
 

 

 

사용한 알고리즘: counting 정렬 (계수 정렬) 

- index 위치에 정렬할 숫자의 갯수를 세어서 넣어주는 알고리즘 이용

 

 

중요한 포인트는 이제 cnt  array 를 볼 때 cnt 에 들어갈 줄의 수가 10000까지 라고 문제에서 지정해줬기 때문에 이를 지정해줘야함!