728x90
문제:https://www.acmicpc.net/problem/10989
코드:https://github.com/irerin07/AlgorithmStudyBaek/blob/master/src/baekjoon/baekjoon10989.java
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class baekjoon10989 {
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[] arr = new int[10001];
for(int i = 0; i < n; i++){
arr[Integer.parseInt(br.readLine())]++;
}
for (int i = 1; i < 10001; i++) {
while (0 < arr[i]--) {
bw.write(i + "\n");
}
}
br.close();
bw.close();
}
}
"수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있다."
수의 범위만큼의 크기를 가진 배열을 만들어서
각 배열의 i마다 각 수가 몇번 나왔는지 저장을 한다.
모든 수의 입력이 끝났다면 맨 처음부터 각 인덱스의 있는 수를 하나씩 빼면서 해당 인덱스를 출력한다.
10 5 2 3 1 4 2 3 5 1 7
위와 같은 예제가 주어지는데
맨 앞의 수는 몇개의 수를 정렬해야하는지 나타내는 수이고
그 다음부터가 정렬을 해야 할 숫자들이다
위의 수를 카운팅 정렬을 사용하면 다음과 같이 저장이 된다.
arr
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ... |
0 | 2 | 2 | 2 | 1 | 2 | 0 | 1 |
5->arr[5]++
2->arr[2]++
3->arr[3]++
1->arr[1]++
4->arr[4]++
2->arr[2]++
3->arr[3]++
5->arr[5]++
1->arr[1]++
7->arr[7]++
주어진 예제에서
1은 총 두 번나오고
2와 3 그리고 5 역시도 총 두 번씩 나온다.
4와 7은 한 번씩 등장하므로 위와 같이 저장이 된다.
이제 반복문을 통해 맨 첫번째 i부터 순서대로 i를 element만큼씩 출력 해 주면 된다.
1
1
2
2
3
3
4
5
5
7
728x90
'알고리즘' 카테고리의 다른 글
[백준] 피보나치 2 [자바/Java] (0) | 2020.06.07 |
---|---|
[백준] 크로아티아 알파벳 [Java/자바] (0) | 2020.04.24 |
[프로그래머스] [1차] 비밀지도 [Java/자바] (0) | 2020.04.07 |
[프로그래머스] 자릿수 더하기 [Java/자바] (0) | 2020.04.05 |
[프로그래머스] 이상한 문자 만들기 [Java/자바] (0) | 2020.04.05 |