[Java] BJ.10989 수 정렬 3

 

 

10989번: 수 정렬하기 3

 

풀이

처음 풀이로 단순히 Array.sort로 시도했으나 시간 초과가 발생하여 Timsort를 사용하는 Collection.sort을 사용했는데 이것은 메모리 초과가 발생했다.

그래서 10000만큼의 int 배열을 만들어 Counting sort를 사용했음에도 시간 초과가 발생했다. 그래서 StringBuilder까지 동원하니 해결이 되었다.

 

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

public class BJ_10989 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int [] arr = new int[10000001];

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

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

        System.out.println(sb);
    }
}

 

if문을 활용한 조건문을 while문으로도 바꿔 보았다.

 

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

public class BJ_10989 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int [] arr = new int[10001];

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

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

        System.out.println(sb);
    }
}