[백준 10989] 수 정렬하기 3

#include<cstdio>
int arr[10000002];
void swap(int *ar, int a, int b) {
    int temp=ar[a];
    ar[a]=ar[b];
    ar[b]=temp;
}
void quicksort(int *ar, int start, int end) {
    int pivot=ar[start];
    int left=start+1;
    int right=end;
    
    while(left<=right) {
        while(ar[left]<=pivot) left++;
        while(ar[right]>pivot) right--;
        
        if (left<=right)
            swap(ar,left,right);
    }
    if(start<end) {
        swap(ar,start,right);
        quicksort(ar,start,right-1);
        quicksort(ar, right+1, end);
    }
}
int main(void)
{
    int n;
    scanf("%d", &n);
    
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    quicksort(arr,0,n-1);
    for(int i=0; i<n; i++) printf("%d\n", arr[i]);
    return 0;
}

 처음에 아무 생각 없이 했을 때는 숫자가 크네? -> 알고리즘 헤더에 있는 정렬은 시간이 오래 걸릴테니 퀵 소트로 하자 -> 메모리 초과가 나서 다시 문제를 봤더니 8MB였다.

그래서 아래처럼 코드를 고쳤다.

#include<cstdio>
int arr[10002];
int main(void)
{
    int n;
    scanf("%d", &n);
    
    for(int i=0,t; i<n; i++){
        scanf("%d", &t);
        arr[t]++;
    }
    
    for(int i=1;i<=10000; i++) {
        if (arr[i]!=0) {
            for(int j=0; j<arr[i]; j++)
                printf("%d\n", i);
        }
    }
    return 0;
}

- JAVA

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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[10001];
 
        int temp=0, max=0;
        for(int i=0; i<n; i++) {
            temp = Integer.parseInt(br.readLine());
            arr[temp]++;
 
            max=(max<temp)?temp:max;
        }
 
 
        for(int i=1; i<=max; i++){
            if(arr[i]!=0){
                for(int j=0; j<arr[i]; j++)
                    sb.append(i).append("\n");
            }
        }
 
        System.out.print(sb);
    }
}