문제 링크
제한
- 시간 제한 : 3 초
- 메모리 제한 : 512 MB
문제
- N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
- 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
- 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
👀 풀이
- 자바는 제한시간 3초에 메모리 제한은 512라 컬렉션을 쓸 수 없었다.(처음에 컬렉션 sort 써 봤는데 메모리 초과됨 ㅠ)
- int 배열 메모리 계산해 보니까 합병정렬을 할 수 있을 정도가 되어서 합병정렬을 구현했다.
- N의 최대값 10,000,000 * 4byte(int) = 40,000,000byte = 39,062kb = 약 38mb
- 합병정렬은 정렬할 배열과 같은 크기의 배열이 하나 더 필요하기 때문에 38 * 2 = 약 76mb
- 그래서 자바에서 기본적으로 잡아먹는 메모리를 더해도 통과할 수 있을거 같아서 합병정렬로 풀었는데 시간이 좀 아슬아슬했다.
결과
- 시간 : 2948 ms
- 메모리 : 383572 KB
코드
