백준 10989번
https://www.acmicpc.net/problem/10989

---

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

---

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

---

생각하기

평소에 배열을 생성해야 되는 문제가 나올 때 거의 List를 이용하는 여기서
한번 제대로 통수를 맞았다.

개인적으로 List 생성하는게 편해서 자주 이용했는데 확실히 일반 배열 보다는
List가 당연히 메모리를 많이 잡아먹을 거라는 걸 생각했어야 했는데..
확실히 습관이 무섭다.

Collection.sort(list)는 바로 메모리 초과로 탈락!

역시 방법은 일반 배열이 메모리를 아낄 수 있는 효과적인 방법
배열 생성 후 Arrays.sort()를 사용하니 간신히 통과를 할 수 있었다.

여기서 워낙 간당간당하게 통과한 것 같아서 다른 분들의 코드를 참고하는게 좋겠다 생각해서 한번 찾아보았다.

다른 분들은 Counting Sort를 사용해서 문제를 해결 하셨는데
역시 아직 배울게 많구나라고 느꼈다

첫번째 정렬방식은 Arrays.sort() 함수를 사용하면 되기때문에 간단히 pass

두번째 Counting Sort는 수의 전체 범위에 맞는 배열을 미리 생성한다
문제에서는 범위가 10000보다 작거나 같은 자연수 라고 했으니
0은 제외되고 1 부터 10000이라고 생각하면 된다.

근데 배열은 0부터 시작이니까 전체 배열의 갯수를 100001개라고 생각하고 생성해야된다.

그래서 count 배열이 [10001]로 초기화 되서 생성된 것이다.
(처음에 왜 10001인지 이해 못함..)

이후에 입력되는 숫자를 인덱스로 넣어서 인덱스 배열에 해당하는 값을 1 증가 시켜주는것이다.

예를 들면, 7이라는 숫자가 들어 왔을경우 count[7]의 배열의 값을 1증가 시켜준다
count[7]의 값은 1이 된다. 입력되는 수 모두 해당 과정을 반복하면 입력되는 숫자가 배열에 count되는 방식으로 증가하게 된다.

이후에 출력할 때는 배열을 다시 1부터 시작(자연수 시작이 1이기 때문)해서
while(count[i] > 0)의 조건 반복을 통하면 0 초과의 값을 가진 배열을 차례대로 출력만 하면 자동으로 정렬된 값을 볼 수 있다.

TMI

꺼진 불도 다시보자!
풀은 코드도 다시보자!

근데 귀찮음;;

---

코드

일반 정렬

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

public class Main {

	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[N];

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

		Arrays.sort(arr);

		for(int num : arr) {
			sb.append(num).append('\n');
		}

		System.out.println(sb);
	}
}

---

Counting Sort를 활용한 정렬

import java.io.*;

public class Main {
	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 count[] = new int[10001];
		for(int i=0; i<N; i++) {
			count[Integer.parseInt(br.readLine())]++;
		}

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

		System.out.println(sb);
	}
}