[BOJ/백준 - 10989] 수 정렬하기 3

문제 출처: https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

---

 

	public class BOJ_10989 {
	static int[] arr;
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder sb = new StringBuilder();
	int size = Integer.parseInt(br.readLine());
	arr = new int[10001];
	for(int i=0; i<size; i++){
	arr[Integer.parseInt(br.readLine())]++;
	}
	for(int i=0; i<10001; i++){
	if(size==0){
	break;
	}
	if(arr[i]!=0){
	int j = arr[i];
	while(j>0){
	sb.append(i).append("\n");
	j--;
	size--;
	}
	}
	}
	System.out.print(sb);
	}
	}

view raw BOJ_10989.java hosted with ❤ by GitHub

일단 

수 정렬하기 1,

수 정렬하기 2는 풀었을 것이다

 

근데 해당 문제인 수 정렬하기 3은 문제 밑의 코멘트에

'수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.'

라고 적혀있고 작성 당시 기준 정답 비율이 22~23%이다

 

이걸 보면 따로 알고있는 방법이 없다면 카운팅 정렬을 써야할것을 알 수 있다

근데 카운팅 정렬을 아는가?

 

알면 좋은데 난 몰랐음

그래서 카운팅 정렬이 뭔지 찾아봄

 

어느 글을 읽었더니 '입력값이 정수가 보장되어 있다면 수를 비교하지 않고 하는 정렬' 이런식으로 적혀있었음

수를 비교하지 않음 + '카운팅' 정렬임 -> 아하

 

(입력값+1) 크기의 배열을 만든다음 

배열[입력값]++;

입력이 끝나면 배열을 차례대로 돌면서 카운팅된 만큼 인덱스값을 출력함

 

나는 모두 출력되도 배열의 끝까지 보내는게 싫어서 값을 하나씩 줄일때마다 N도 줄여서

N값이 0이되면 바로 출력하게 해놓았음

 

오늘도 하나 건져간다