문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
풀이
단순 정렬
문제임에도 불구하고 제출 수가 10만이 넘어가는 정답률 20퍼
짜리 문제이다. 다른 문제들과 뭐가 다른지 자세히 살펴보면 메모리 제한이 8MB
임을 알 수 있다. 하지만 받아야하는 수의 개수는 1천만 개이므로 수를 단순히 저장하는 것 만으로 메모리가 초과됨을 예상할 수 있다. 하지만 이것 외에 이 문제의 또 다른 특징이 있는데 바로 모든 수가 10000
보다 작다는 것이다. 즉, 메모리 사용량이 지극히 적은 대신 아주 작은 수만 비교하여 정렬한다. 여기서 떠올려야 할 정렬 알고리즘은 바로 카운팅 정렬
이다.
입력받은 수를 저장하지 않고, 모든 수마다 몇 번 등장하는지만 체크한다.
이 때, 수는 10000
을 넘기지 않으므로 길이가 10000
인 배열을 만들면 모든 수 마다 몇 번 등장하는지 체크할 수 있다. 아래 코드를 통해 확인할 수 있다.
전체 코드
1 |
|
- Post link: https://blog.yjyoon.dev/boj/2021/06/24/boj-10989/
- Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.