«   2022/10   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
Archives
Today
0
Total
96,326
관리 메뉴

차근차근

[백준 10989] 수 정렬하기 3 본문

대학교/Algorithm

[백준 10989] 수 정렬하기 3

SWKo 2020. 4. 4. 01:32

0. 제목

  • 백준 10989 수 정렬하기 3
  • BOJ 10989 수 정렬하기 3
  • C++ 10989 수 정렬하기 3

1. 문제

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

 

10989번: 수 정렬하기 3

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

www.acmicpc.net


2. 풀이

  • 계수 정렬(Counting Sort)를 사용하는 문제이다.
  • 버블 소트와 같은 것을 사용하면 시간 초과가 난다. 계수 정렬은 수의 범위가 작을 때 사용하기에 적합하다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
 
int N;
int num;
int arr[10001];
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> N;
    
    for(int i = 0; i < N; i++){
        cin >> num;
        arr[num]++;
    }
    
    for(int i = 1; i <= 10000; i++){
        for(int j = 0; j < arr[i]; j++){
            cout << i << '\n';
        }
    }
    
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 11004] K번째 수  (0) 2020.04.05
[백준 11652] 카드  (2) 2020.04.04
[백준 10825] 국영수  (0) 2020.04.04
[백준 1182] 부분수열의 합  (0) 2020.03.24
[백준 1987] 알파벳  (0) 2020.03.23
0 Comments
댓글쓰기 폼