[백준10989] 수 정렬하기 - 3 [java]

---

이 문제는 수 정렬하기 3번째 문제인 만큼 더 생각해야할 부분이 있다.

바로 데이터의 양이 너무 많다는 것이다!!

 

따라서 Scanner를 사용해서는 문제를 통과할 수 없고 BufferedReader를 사용해야 한다.

 

Scanner와 BufferedReader의 차이는 값을 입력받을 때 buffer로 한번에 통과시키면 많은 데이터를 받을 때 훨씬 빠르게 처리할 수 있다.

 

또한 배열과 리스트에서도 데이터를 처리할 때 차이가 많이 나게 된다. 따라서 같은 sort이고 Arrays.sort가 시간복잡도가 높고 Collection.sort가 시간복잡도가 작더라도 이 문제처럼 주어진 데이터가 많을 때는 Arrays.sort를 쓰는게 더 좋다.

 

따라서 Arrays.sort와 BufferedReader를 사용하면 문제를 해결할 수 있다.

 

하지만 앞의 올린 글처럼 Arrays.sort는 시간복잡도가 최악의 경우 o(n^2)이 된다. 문제의 테스트 케이스에 최악의 경우가 없어서 통과한 것이므로 다른 방법또한 공부했다.

 

Arrays.sort와 BufferedReader를 사용한 코드

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));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        int[] arr= new int[n];

        for(int i = 0; i<n;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        for(int i = 0;i<n;i++){
            sb.append(arr[i]).append('\n');
        }
        System.out.println(sb);
    }
}

---

sort를 활용하지 않는 방법을 찾았다.

배열의 길이를 먼저 정해주고 거기에 입력받은 수를 인덱스로 그 배열의 값을 더해준다.

배열을 이용한 코드

 

package baekjoon;

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

public class num_sort3 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int[] cnt = new int[10001];
        int n = Integer.parseInt(br.readLine());

        for(int i = 0; i<n;i++){
            cnt[Integer.parseInt(br.readLine())]++;
        }

        br.close();

        for(int i = 1;i<10001;i++){
            while(cnt[i] > 0){
                sb.append(i).append('\n');
                cnt[i]--;
            }
        }
        System.out.println(sb);
    }
}