n번째로 큰 수를 찾는 가장 빠른 방법 (부제: Array는 Vector보다 빠르다)

Tags
C++
Optimization
Date
Jul 17, 2022
Property
Jul 16, 2022 04:19 PM

요약

본 문서에서는 위 문제를 해결하는 아래의 3가지 방법의 각 코드를 공개하고, Array + Sort가 가장 빠름을 증명할 것이다. 언어는 C++14를 사용하였다.
  • Array + Sort
  • Vector + Sort
  • Priority Queue
 

문제

첫번째 줄에는 n과 k가 입력되고, 다음 라인에는 n 만큼의 수가 입력된다. k번째로 큰 수를 출력하는 게 이번 문제의 목표이다.
  • 예제 입력
    • 5 2 4 1 2 3 5
  • 예제 출력
    • 2
 

각 방법 별 코드

Array + Sort
#include <bits/stdc++.h> #include <algorithm> #define MAX 5000000 using namespace std; int n, k; int arr[MAX]; int main(void){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> n >> k; int tmp; for(int i = 0; i < n; i++){ cin >> arr[i]; // v.push_back(tmp); } sort(arr, arr+n); cout << arr[k-1] << '\n'; }
Vector + Sort
#include <bits/stdc++.h> #include <algorithm> using namespace std; int n, k; vector<int> v; int main(void){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> n >> k; int tmp; for(int i = 0; i < n; i++){ cin >> tmp; v.push_back(tmp); } sort(v.begin(), v.end()); cout << v[k-1] << '\n'; }
Priority Queue
#include <bits/stdc++.h> #include <queue> using namespace std; int n, k; priority_queue<int, vector<int>, less<int>> q; int main(void){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> n >> k; int tmp; for(int i = 0; i < k; i++){ cin >> tmp; q.push(tmp); } for(int i = k; i < n; i++){ cin >> tmp; if(q.top() > tmp){ q.pop(); q.push(tmp); } } // for(int i = 1; i < k; i++){ // cout << q.top() << '\n'; // q.pop(); // } cout << q.top() << '\n'; }
 

결과

본 실험 결과는 백준의 채점 결과에서 확인된 수치를 바탕으로 작성하였다. 언어는 C++14를 사용하였다. Memory, Time은 낮을 수록 좋으며, 가장 좋은 수치는 굵은 글씨로 표기하였다.
Method
Memory (KB)
Time (ms)
Array+Sort
21,552
1,044
Vector+Sort
51,300
1,112
Priority Queue
51,300
1,084
벡터 구조 상 각 요소들이 메모리 내에 흩뿌려져있기 때문에 주소를 가지고 있어야한다. 때문에Vector+Sort 방법을 사용했을 때, Array+Sort보다 메모리 공간을 크게 점유한다.
Priority Queue도 마찬가지로 각 요소의 메모리 주소를 저장해야한다. 따라서 메모리 Array+Sort보다 메모리 공간을 크게 점유하는 것을 볼 수 있다. (명확한 것은 아니지만, 큐에 수를 k개 만큼만 저장하도록 설계했기 때문에 Vector+Sort보다 시간이 적게 걸린 것으로 보인다. 다른 이유도 존재할 것 같다. Array+Sort보다 느린 이유에 메모리 할당 시간도 존재할 것 같은데 잘은 모르겠다.)

결론

보다 Array+Sort를 사용했을 때, Vector+Sort와 Priority Queue 대비 메모리 공간, 실행시간 면에서 이점이 있음을 확인하였다.