문제 출처: https://www.acmicpc.net/problem/10989

문제 설명

그냥 받은 수를 오름차순으로 정렬해서 출력하면 끝이다.

문제 풀이

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String args []) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int total = Integer.parseInt(br.readLine());
        int[] arr = new int[total];
        for (int i = 0; i < total; i++)
            arr[i] = Integer.parseInt(br.readLine());
        Arrays.sort(arr);
        for(int a : arr)
            bw.write(a + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

그냥 간단하게 이렇게 해도 통과는 된다.

이제 통과 하고 이 코드보다 압도적으로 속도가 빠른 코드를 쓴 사람들의 정렬 코드를 확인해 보겠다.

수 정렬하기 2 에서 위 코드보다 빠른 코드

import java.io.*;

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

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

        for (int i = 0; i < arr.length; i++) {
            if(arr[i]) sb.append((i - 1000000)).append('\n');
        }

        System.out.println(sb);
    }
}

boolean array를 활용해서 O(N)으로 끝내서 O(NlogN)인 Arrays.sort() 보다 빠르게 끝냈다.

수 정렬하기 3 에서 위 코드보다 빠른 코드

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

public class Main {

    static int[] arr = new int[10003];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; ++i) {
            int num = Integer.parseInt(br.readLine());
            ++arr[num];
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= 10000; ++i) {
            for (int j = 0; j < arr[i]; ++j) {
                sb.append(i).append("\n");
            }
        }
        System.out.println(sb);
    }
}

int array를 활용해 O(N)에 가까운 속도를 냈다. nested loop같아보이지만 중복되는 수가 발생할 것까지 고려해서 처리했다.