https://www.acmicpc.net/problem/10989
10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
10M의 숫자를 3초 안에 오름차순으로 sorting 하는 문제입니다.
처음에는 간단하게 Insertion Sort를 시도 했으나, 시간이 초과되었습니다.
그 다음은 STL에서 제공하는 heap Sort를 시도 했으나, 이번에는 메모리가 초과하였습니다.
세번째는 입력 값이 10K 이하 자연수이기에 10K 사이즈의 Array를 두고, Array 값에 들어온 횟수를 저장해보았습니다.
Insertion Sort보다는 더 오래 갔지만 결국 시간이 초과되었습니다.
아마 Sort를 직접 구현하게 하려는 문제인 것 같습니다.
그래서 내일은 Merge Sort를 직접 구현해보려 합니다.
'개발일지 > Algorithm' 카테고리의 다른 글
| 20.06.24 개발일지 - 수 정렬하기 3 (0) | 2020.06.24 |
|---|---|
| 20.06.24 개발일지 (0) | 2020.06.24 |
| 20.06.17 개발일지 - 가장 긴 증가하는 부분 (0) | 2020.06.17 |
| 20.06.16 개발일지 - 가장 긴 증가하는 부분 수열 (0) | 2020.06.16 |
| 20.06.15 개발일지 - 가장 긴 증가하는 부분 수열 (0) | 2020.06.15 |