백준 10989 [수 정렬하기 3]

출처 : www.acmicpc.net/problem/10989

 

시간제한                  메모리제한        제출                           정답                맞은 사람           정답 비율

3 초 (하단 참고)

8 MB (하단 참고)

100576

22561

16959

22.946%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

 

 

시간제한 안에는 들어온다고 생각해서 vector를 전역변수로 두고, sort 알고리즘 써서 풀어봤다.

하지만 정답률이 낮은 데에는 이유가 있듯 메모리 초과가 났다.

 

조금 머리를 써야했던 문제.

입력의 조건인 "10000보다 작거나 같은 자연수"를 사용해야 했다.

따라서 arr[10001]을 선언해주고, 입력 수가 들어올 때마다 해당 index를 더해준다.

그리고 해당 index가 입력된 횟수만큼 출력해주면 되는 문제였다