[BOJ] 10989번 수 정렬하기 3 - JAVA

## Java 풀이 시 유의사항 ##
클래스명은 Main 으로 작성해야함!

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

/* 풀이 1 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]).append("\n");
        }
        System.out.println(sb);
    }
}

/* 풀이 2 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws IOException {
        // 수의 범위 (0 ~ 10000) 사실상 0은 제외
        int[] cnt = new int[10001];
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < N; i++) {
            // 해당 인덱스의 값을 1 증가
            cnt[Integer.parseInt(br.readLine())] ++;
        }
 
        br.close();
 
        StringBuilder sb = new StringBuilder();
 
        // 0은 입력범위에서 없으므로 1부터 시작
        for(int i = 1; i < 10001; i++){
            // i 값이 개수가 0 이 될 때 까지 출력 (빈도수를 의미)
            while(cnt[i] > 0){
                sb.append(i).append('\n');
                cnt[i]--;
            }
        }
        System.out.println(sb);
    }
}

📄 해설

• Arrays.sort 메소드를 사용하여 정렬을 하면 되는 문제
• 다만 이 문제에는 시간 제한이 있으므로, BufferedReader 와 StringBuilder 를 필수적으로 사용해야함
• Arrays.sort 메소드의 시간 복잡도가 최악의 경우 O(N2) 인 것을 고려하면, 훌륭한 풀이라고 보기가 어려움
• 위 문제 해결을 위해 계수정렬(Counting Sort) 알고리즘을 사용하면 시간복잡도는 O(N+K) 로 줄어들어, 아래와 같이 성능에서의 큰 차이를 보임
  
• 위가 계수정렬을 사용한 풀이 2 의 결과이고, 아래가 Arrays.sort 메소드를 사용한 풀이 1 의 결과