https://www.acmicpc.net/problem/10989
문제분석
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이기 때문
코드
#include<iostream>
using namespace std;
int num;
int arr[10001]; // 배열의 인덱스는 1부터 시작하므로 최대값보다 +1
int main(){
ios_base::sync_with_stdio(false)
cin.tie(NULL);
cout.tie(NULL);
int temp;
cin >> num;
for (int i = 0; i < num; i++) {
cin >> temp;
arr[temp]++; // 입력으로 들어온 숫자에 해당하는 인덱스의 값 ++
}
for (int i = 1; i < 10001; i++) {
for (int j = 0; j < arr[i]; j++) {
printf("%d\n", i); // 그냥 출력하지 않고 for문을 한번 더 사용하는 이유
// => 입력으로 들어온 것 중 동일한 수가 있을 수 있기 때문
}
}
return 0;
}
문제풀이
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인 배열을 하나 생성 후, 각 원소가 몇번 등장하는지 세어준다.
그리고 배열을 처음부터 끝까지 방문하면서 해당 숫자를 등장한 횟수만큼 출력하면 끝!!
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
백준 1107번 리모컨 <브루트포스> (0) | 2022.07.12 |
---|---|
다익스트라 백준 1238번 파티 (0) | 2022.07.12 |
시뮬레이션 BOJ 3190번 (0) | 2022.07.12 |
DP의 대표적 문제 - BOJ 1463번 (0) | 2022.07.12 |
[백준/C++] 9012번 괄호 (0) | 2022.07.12 |