📌 문제 1. 최소힙 구현

✅ 문제

• 테스트 예제
  

✅ 아이디어

최소힙 : 작은 값이 우선순위가 높음 --> greater<int>
--> 오름차순으로 정렬
⭐ 입력 받는 값이 0이면 pop하고 출력
⭐ 입력 받는 값이 0이 아니면 우선순위 큐에 push
⭐ 우선순위 큐가 empty인 경우에는 0출력 (예외 처리)

✅ 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){
    int N,num;
    priority_queue<int, vector<int>,greater<int>> pq;
    vector<int> v;

    cin >> N;

    for(int i = 0 ; i < N ; i++){
        cin >> num;

        // num이 0이면 요소를 출력해야함
        if(num == 0){
            if(pq.empty()) v.push_back(0); // 예외처리
            else{ // pop 요소 프린트하기 
                v.push_back(pq.top());
                pq.pop(); 
            }
        }  
        // num이 0이 아니면 최소힙에 요소를 추가해야함
        else pq.push(num);
    }

    for(int i = 0 ; i < v.size(); i++){
        cout << v[i] << endl;
    }
}

📢 코드 설명

• vector<int> v : 벡터 v는 출력 값을 저장하기 위해 사용됨.
• if(num == 0) : 입력된 값이 0인 경우, 힙에서 가장 작은 값을 꺼내 출력하는 연산 수행
• if(pq.empty()) : 만약에 최소힙 pq가 비어있으면 출력할 값이 없으므로 v벡터에 0저장
• else : 최소힙이 비어 있지 않으면, 최소힙에서 가장 작은 값을 가져오고 (pq.top()), 그 값을 v 벡터에 저장한 후(v.push_back(pq.top())), 힙에서 해당 값을 제거(pq.pop());)
• else pq.push(num) : num이 자연수면 num을 최소힙에 추가함.

📌 문제 2. K번째 수

✅ 문제

✅ 접근 방법

N개의 수를 모두 정렬할 필요가 없는 이유
--> N개의 수 중에서 K개의 수만으로도 K번째 큰 수를 알 수 있기 때문에

✅ 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
  
int main(){
  int N,K;
  cin >> N >> K;
  priority_queue<int, vector<int>, greater<int>> pq;
  
  for(int i = 0 ; i < N ; i++){
      int num;
      cin >> num;
      pq.push(num);
}
  for(int i = 0 ; i < K - 1; i++){
      pq.pop();
  }
  cout << pq.top() << endl;
  return 0;
}

📌 문제 3. N번째 큰 수

✅ 문제

✅ 접근방법

N^2를 정렬하면 시간제한에 걸려서 fail이 됨 --> 아이디어 필요
⭐⭐ 한 개씩 PQ를 삽입해 가면서 PQ의 개수가 N을 넘어가면 삭제
--> 그러면 N번째 큰 수가 top에 남음
⭐⭐ 최소 힙의 특성 --> 그 안에서 가장 작은 값이 항상 맨 위에 있음
--> 우리는 N번째로 큰 수를 찾아야 하므로, 상위 N개의 큰 수만 관리하는 방식이 필요함

❔왜 Min Heap의 top이 5번째로 큰 수가 될까?

• N = 5 라면, 우리는 총 25개의 수 중에서 5번째로 큰 수를 찾아야함
  --> 최소힙의 크기를 5로 유지하면서 계속해서 새로운 수를 삽입하고, 작은 수는 제거하는 방식으로 상위 5개의 큰 수만 관리함
  📢📢 최종적으로 최소힙 안에 남아 있는 5개의 수는 배열 전체에서 상위 5개의 큰 수임.
  

✅ 코드

⭐⭐ 내가 짠 코드 수정해야할 부분

⚠️ if(pq.size() > N) pq.pop(); 을 두 번째 for문 안에 같이 넣어줘야함!!
⚠️ pq.pop()을 각 행 마다 수행해야함 --> 내 코드는 마지막 행에서만 pop()이 됨.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main(){
    int N,num;
    cin >> N;

    priority_queue<int,vector<int>,greater<int>> pq;

    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            cin >> num;
            pq.push(num);
        }
        if(pq.size() > N) pq.pop();
    }
    cout << pq.top() << endl;
    return 0;
}

정답 코드)

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue<int, vector<int>, greater<int>> pq;	// minHeap
    int N, num;

    cin >> N;	// 데이터 N 읽기

    for (int i = 0; i < N; i++) {	// minHeap에서 N개의 큰 수 유지
        for (int j = 0; j < N; j++) {
            cin >> num;		// N^2개의 데이터 읽어서
            pq.push(num);	// minHeap에 추가
            if (pq.size() > N) {	// minHeap의 크기가 N을 초과하면
                pq.pop();		// minHeap에서 제거
            }
        }
    }

    cout << pq.top();	// minHeap의 top이 N번째 큰 수
}