수 정렬하기 2

제출코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int repeat = Integer.parseInt(br.readLine());
        int[] array = new int[repeat];
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for (int i = 0; i < repeat; i++) {
            int number = Integer.parseInt(br.readLine());
            array[i] = number;
        }

        Arrays.sort(array);
        for (int i : array) {
            bw.write(String.valueOf(i));
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

• Arrays.sort()를 사용하여 풀었다. 처음에 sysout을 사용했을 때 시간 초과가 나서 bw를 사용해서 풀었더니 통과가 되었다.

• 이 문제의 핵심은 Arrays.sort() 대신 Collections.sort()를 사용하는 것이었다. (자바 7이전 기준)

• 자바 7 이후로는 Arrays.sort, Collections.sort 모두 팀소트 알고리즘을 사용한다.
  둘 다 평균 및 최악의 경우 O(N log N)의 시간복잡도를 갖는다.

결론

1. 자바 11 이후의 Arrays.sort, Collections.sort는 TimSort 알고리즘을 사용한다. 모두 평균 및 최악의 경우 O(N log N)의 시간복잡도를 갖는다.