1. Problem 📃

[ 수 정렬하기 3 ]

https://www.acmicpc.net/problem/10989

[ 문제 ]

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

2. Input ⌨️

[ 입력 ]

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

3. Output 🖨

[ 출력 ]

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

4. Example 📚

[ 입출력 예시 ]

5. Solution 🔑

처음에 값들을 배열에 넣어주고 sort()시켜서 풀어보았다 그런데 여기 클래스에서는 이렇게 간단한 방식이 나오면 느낌이 쎄하다... "시간 초과"가 떴다.
그래서 검색해보니 카운팅 정렬을 이용해야한다고한다.


1. 몇 개의 명령을 입력받을지에 대한 변수(N)을 입력받는다.
값들을 담을 배열 변수(arr)의 크기를 10001의 길이만큼 선언해준다.
들어오는 값은 10000이하의 자연수이므로 10000이지만 보기 편하게 1부터 탐색할 것이므로 100001로 해주었다.


2. N개의 명령만큼 배열 변수 arr에 해당하는 입력된 값의 인덱스를 증가(++)시켜준다.
이렇게 되면 각 배열의 인덱스값이 몇 번 나왔는지 카운팅해준다.


3. 다시 arr를 탐색하며 인덱스의 값만큼 루프를 돌려 StringBuilder(sb)에 값을 삽입하며 개행해준다.


4. 최종 StringBuilder(sb)를 출력해준다.

6. Code 💻

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		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())]++;
		}
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr[i]; j++) {
				sb.append(i).append('\n');
			}
		}
		System.out.println(sb);
	}
}

7. Growth 🍄