[C++] 백준 1655 - 가운데를 말해요(우선순위 큐를 적용해야 하는데, 이분 탐색 활용)

0. [c++] 백준  -

https://www.acmicpc.net/problem/1655

1. 풀이

자세한 설명은 소스코드에서 주석으로 달아놓았다.

간단하게 접근방법을 설명하자면, 문제를 해결하기 위해서는 배열을 항상 오름차순으로 유지해야하는 것이 포인트였다.

오름차순으로 유지하기 위해서 삽입정렬을 활용했다고 생각하면 되는데, 숫자를 넣는 동작에서 정렬된 배열이 흩어지지 않도록 해준 것이 포인트였다.

이때, 탐색 시간을 줄이기 위해서 이분 탐색을 적용해주었다.

시간복잡도를 구해보자. vector에서 insert는 선형시간복잡도 O(1)이고, 이분 탐색의 시간복잡도는 O(log N)이며, 이때, 반복하는 횟수는 N번으로 최종적인 시간복잡도는 O(N log N)을 구할 수 있다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

#include<iostream> #include<vector>   using namespace std;   vector<int> arr;   void push(int num) {     if (arr.empty()) {         arr.push_back(num);         cout << num << "\n";         return;     }     //이분 탐색을 활용해 자신보다 작은 수의 개수를 찾는다.     int low = 0, high = arr.size() - 1, mid;     int ret = 0;     while (low <= high) {         mid = (low + high) / 2;         if (arr[mid] <= num) {             if (ret < mid) {                 ret = mid;             }             low = mid + 1;         }         else             high = mid - 1;     }       //만일 자기보다 작은 수가 0이라면, 가장 작은 경우인지 확인을 한다.     if (!ret && arr[0] > num)         //가장 작은 경우는 맨 앞에 num을 삽입한다.         arr.insert(arr.begin() + ret, num);     //일반적인 경우라면 작은 수 바로 앞에 삽입한다.     else         arr.insert(arr.begin() + ret + 1, num);          //최종적으로 중간값을 출력한다.     if (arr.size() % 2)         cout << arr[arr.size() / 2] << "\n";     else         cout << arr[arr.size() / 2 - 1] << "\n"; }   int main() {     cin.tie(0);     cin.sync_with_stdio(0);       int N, num;     cin >> N;       for (int i = 0;i < N;i++) {         cin >> num;         push(num);     }       return 0; }   Colored by Color Scripter

cs

3. 참고

- insert의 시간복잡도

https://stackoverflow.com/questions/25218880/why-is-stdvectorinsert-complexity-linear-instead-of-being-constant

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!