[백준/C++] 10989번 수 정렬하기 - 3
N개의 수가 주어지고, 이를 오름차순으로 정렬하는 문제이다.
입력으로는 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력으로는 둘째 줄부터의 입력들을 오름차순으로 정렬하면 된다.
예를 들어, 첫째 줄에 5가 주어지고 두번째 줄부터 차례로 3 6 9 3 6 이 주어졌다고 했을 때,
출력으로 3 3 6 6 9를 만들면 된다.
그러나 이 문제는 시간제한 및 메모리 제한이 존재한다.
즉, 입력받은 수를 다 저장하고 다시 정렬하고자 하면 8MB의 메모리를 초과해버린다.
-> 4byte의 수가 총 10^7개 만큼 올 수 있으니 이는 4*10^7byte로 40MB이기 때문
코드
문제풀이
1. 시간복잡도 해결
위 코드의 이중 for문은 O(N^2)의 시간복잡도를 가지게 되고, 그로 인해 문제가 요구하는 시간을 초과해버리는 문제가 발생한다.
위 코드는 c와 c++의 표준 stream의 동기화를 끊어주는 역할을 한다.
따라서 cin과 cout의 속도가 빨라져 시간초과 문제를 해결할 수 있다.
또는, cin과 cout 대신 scanf와 printf를 사용한다면 위 코드 없이도 해결 가능하다.
endl 대신 \n을 써주는 것도 좋다.
2. 공간복잡도 해결
앞서 말했듯, 메모리제한으로 인해 sort()함수를 사용할 수 없다.
정렬해야 하는 수의 범위가 1 이상 10,000 이하이므로 계수정렬(Counting sort)을 이용한다.
계수정렬이란? 원소들간 비교 없이 정렬을 할 수 있는 알고리즘이다.
(음수, 소수에는 불가능)
(수의 범위가 상대적으로 작은 경우에 유용한 정렬)
크기가 10,000인 배열을 하나 생성 후, 각 원소가 몇번 등장하는지 세어준다.
그리고 배열을 처음부터 끝까지 방문하면서 해당 숫자를 등장한 횟수만큼 출력하면 끝!!
원본 : https://blog.naver.com/oh2279/222618248826
[백준/C++] 10989번 수 정렬하기 - 3
https://www.acmicpc.net/problem/10989 문제분석 N개의 수가 주어지고, 이를 오름차순으로 정렬하는 문제...
blog.naver.com