[백준 문제풀이] 10989번 수 정렬하기3(with. JAVA)

백준 10989번 문제 바로가기

이번 문제는 2750번, 2751번과 비슷한 유형의 정렬 문제이다. 두 문제와 다른 점은 입력 값의 범위와 입력 값이 중복되어도 된다는 점에 있다. 같은 값이 여러 번 있을 수 있는 배열을 정렬해야하기 때문에 나는 카운팅 정렬을 사용하여 문제를 풀었다. (카운팅 정렬 참고)

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

public class P10989 {
	// 2750, 2751 문제와의 차이 -> 중복되는 숫자가 존재 
	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());
        
		// 0 < 배열의 원소 ≤ 10,000이고, 배열의 인덱스는 0부터 시작하므로
		// 배열의 크기는 10,000+1인 10,001
		int [] arr = new int[10001];
		
		for(int i = 0; i < n; i++) {
			// 카운팅 정렬을 사용 할 것이므로
			// arr[i]에는 i가 입력 될 때마다 +1을 해줌
			arr[Integer.parseInt(br.readLine())]++;
		}
		
		br.close();
		
		for(int i = 1; i < arr.length; i++) {
			// arr[i]에는 i라는 숫자가 몇 번 입력되었는지 카운트한 숫자가 들어있으므로
			// 1이상인 경우에만 i를 출력하면 됨
			while(arr[i] > 0) {
				sb.append(i).append('\n');
				arr[i]--;
			}
		}
		
		System.out.println(sb);
	}
}