10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
N의 범위는 10^7, 각 원소의 크기는 10^4
다 넣고 정렬하기에는 중복된 수가 많을 뿐 더러 N의 크기가 크기 때문에 NlogN의 복잡도를 가지는 sort, map등을 사용할 수 없다.
다행히 범위가 적기 때문에 하나의 길이를 그냥 메모리에 저장하고 갯수의 크기를 저장하면 된다.
이걸 카운팅 정렬이라고 부른다 카더라
정렬? 이라고 부르기엔 음,,,
'알고리즘' 카테고리의 다른 글
| 2661 백준 (0) | 2021.03.06 |
|---|---|
| 15686 백준 (0) | 2021.03.06 |
| 5430 백준 (0) | 2021.03.04 |
| 1874 백준 (0) | 2021.03.03 |
| 1920 백준 (0) | 2021.03.01 |