[백준 10989] 수 정렬하기 3

 

 

수의 개수가 10,000,000 이라 배열에 모두 담게되면 메모리 초과로 풀 수 없다.

 

정렬할 수가 10000 이하 라는것을 이용하여 수가 입력된 개수를 세어 정렬하는 카운팅 정렬(계수 정렬)으로 풀 수 있다.

 

 

풀이 1

 

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        int a[] = new int[10001];
        for(int i=0; i<n; i++) {
            int num = Integer.parseInt(br.readLine());
            a[num]++;
        }
        
        for(int i=1; i<=10000; i++) {
            for(int j=0; j<a[i]; j++) {
                bw.write(i + "\n");
            }
        }
        br.close();
        bw.flush();
        bw.close();
    }
}

 

10001 크기의 배열에 입력된 수의 개수를 저장한다.

인덱스를 개수 만큼 출력해주면 원하는 출력을 만들어 낼 수 있다.

 

 

 

풀이 2

 

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        int a[] = new int[10001];
        for(int i=0; i<n; i++) {
            int num = Integer.parseInt(br.readLine());
            a[num]++;
        }
        
        for(int i=1; i<=10000; i++)
            a[i] += a[i-1];
        
        for(int i=1; i<=10000; i++) {
            for(int j=0; j<(a[i] - a[i-1]); j++)
                bw.write(i + "\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }
}

 

풀이 방법은 유사하다.

 

카운트 배열로 카운트 합 배열을 만들어 푸는 일반적인 카운팅 정렬을 비슷하게 쓴 코드이다.